UNB Scholar Research Repository :: Browsing by Author "Nickerson, Bradford, G."

Browsing by Author "Nickerson, Bradford, G."

Now showing 1 - 20 of 24

A Data Structure for I/O Efficient Search of Objects Moving on a Graph
(2009) Le, Thuy, T., T.; Nickerson, Bradford, G.
We present a spatio-temporal data structure called minimum I/O Graph Strip Tree (minGStree) to index moving objects on a graph. The minGStree is designed to efficiently answer time instance and time interval queries about the past positions of moving objects. The minGStree uses Θ( n ) blocks of external memory, where n B is the number of moving object instances (unique entries of moving objects) and B is the I/O block size. For n moving object instances randomly distributed on the E edges of a graph over a time domain [0, T ], the expected number of I/Os required to determine the moving objects intersecting one edge (for both time instance queries and time interval queries) in a minGStree is O(logB ( n ) + k), where k is the number E of disk blocks required to store the answer. We anticipate this data structure will be practical to implement.
A dynamic data structure for efficient bounded line range search
(2010) Le, Thuy, T.; Nickerson, Bradford, G.
A dynamic data structure for efficient axis-aligned orthogonal range search on a set of n lines in a bounded plane is presented. The algorithm requires O(log n + k) time in the worst case to find all lines intersecting an axis aligned query rectangle R, for k the number of lines in range. O(n + lambda) space is required for the data structure used by the algorithm, where lambda is the number of intersection points among the lines. Insertion of a new rightmost line l or deletion of a leftmost line l requires O(n) time in the worst case. For a sparse arrangement of lines (i.e., for lambda = O(n)), insertion of a rightmost line l or deletion of a leftmost line l requires O (√n) expected time.
A Formal Grammar for Geographic Information Metadata
(2000) Nickerson, Bradford, G.; Teng, Ying
An investigation of multi-level k-ranges
(2004) Falconer, Sean, M.; Nickerson, Bradford, G.
Multi-level k-ranges are an efficient theoretical data structure for range searching introduced by J. L. Bentley and H. A. Maurer. Bentley and Maurer showed that a 1-level k-range offers O(k log N + A) query time, where k is the number of dimensions, N is the number of data points and A is the number of points matching the query at the expense of O(N[superscript 2k−1]) storage. They also introduced the multi-level k-range, which offers slightly slower query time but with O(N[superscript 1+e]) storage for any fixed values of k and e > 0. In this paper, we investigate an implementation of the multi-level k-range data structure. The l-level k-range is compared to naive and R*tree search over N randomly generated k-d points. We show that the R*tree search is significantly faster and that even naive search is faster for most test cases. Results indicate that multi-level k-ranges are not competitive due to their (previously unreported) complexity. Our results indicate that l-level k-ranges require Q(N, k, l) = O((2l)[superscript (k−1)](log N + A)) time for range search. We show that S(N, k, l) = O(N[superscript 1+2(k−1)/l]) and when N does not equal a[superscript l] where a and l are positive integers, S(N, k) = O(N[superscript 1+2(k−1)]/ log[subscript 2] N).
Applications of the extension principle to the plane
(1995) Xu, Xiubin; Nickerson, Bradford, G.
Approximate Orthogonal Range Search using Patricia Tries
(2005) Shi, Qingxiu; Nickerson, Bradford, G.
We use Patricia tries to answer E-approximate orthogonal range search on a set of n random points and rectangles in k-dimensional space. Given n k-dimensional random points or rectangles and a k-dimensional query rectangle, E-approximate orthogonal range query counts (or reports) the points in the query rectangle or the rectangles intersecting the query rectangle, allowing errors near the boundary of the query rectangle. Points within a distance of a function of E the boundary of the query rectangle might be misclassified. The approximate orthogonal range search time using Patricia tries is determined theoretically to be O(k log n/E[superscript k-1]) for cubical range queries. Patricia tries are evaluated experimentally for E-approximate orthogonal range counting and reporting queries (for 2 < k < 10 and n up to 1,000,000) using uniformly distributed random points and rectangles, and we compared the performance of the Patricia trie for k-d points with the k-d tree and the adaptive k-d tree. The experimental results show that allowing small errors can significantly improve the query execution time of the approximate range counting. For epsilon = 0.05, an average of 50% fewer nodes are visited for the Patricia trie (compared to the exact range search).
Data Structures for Moving Objects on Fixed Networks
(2007) Thi Thu Le, Thuy; Nickerson, Bradford, G.
Decreasing Radius K-Nearest Neighbor Search using Mapping-based Indexing Schemes
(2006) Shi, Qingxiu; Nickerson, Bradford, G.
A decreasing radius k-nearest neighbor search algorithm for the mapping-based indexing schemes is presented. We implement the algorithm in the Pyramid technique and the iMinMax(θ), respectively. The Pyramid technique divides d-dimensional data space into 2d pyramids, and the iMinMax(θ) divides the data points into d partitions. Given a query point q, we initialize the radius of a range query to be the furthest distance of the k candidate nearest neighbors from q in the pyramid (partition) which q is in, then examine the rest of the pyramids (partitions) one by one. After one pyramid (partition) is checked, the radius of the range query decreases or remains the same. We compare the decreasing radius k-nearest neighbor search algorithm with the increasing radius k-nearest neighbor search algorithm using the Pyramid technique and the iMinMax(θ). Moreover, the decreasing radius k-nearest neighbor search performance of these two mapping-based indexing schemes is compared to the BBD-tree, the R*-tree and naive search. Experimental results show that our decreasing radius k-nearest neighbor search algorithm for the mapping-based indexing schemes is efficient when d <= log2 n.
Deterministic skip lists for k-dimensional range search
(1995) Lamoureux, Michael, G.; Nickerson, Bradford, G.
This report presents a new data structure for multidimensional data which is based on an extension of the deterministic skip list data structure projected into k-dimensions. The data structure is labeled the k -d Range DSL and it allows for efficient multidimensional range search on point data. This structure supports fast insertions, deletions, and search and the k-d Range DSL is shown to be opthual (i.e. O(lgkn + t) to find t points in range) for k-d range search on n points in a dynamic environment with a pointer based memory model where we impose restrictions on worst-case search time, dynamic operations, and storage. The structure is extendible and it does pennit for multidimensional semi-infinite range queries in an equivalent !hue. The k-d Range DSL, by nature of the skip list structure, is well suited for range search in a parallel processing environment. Algorithms for building, insertion, deletion, and range search are provided for the data structure along with proofs of validity and worst-case complexity for these operations. Also, complete working code in (Borland's Turbo) Pascal is provided in the appendices. Keywords: dynamic data structures, algorithms, range search, orthogonal range query, multidimensional data, skip lists, searching, worst-case complexity
Efficient Search of Path-Constrained Moving Objects
(2008) Nickerson, Bradford, G.; Thi Thu Le, Thuy
We present a spatio-temporal data structure called the Graph Strip Tree (GStree) for indexing objects constrained to move on a planar graph. The GStree is designed to efficiently answer range queries about the current or past positions of moving objects. To test the efficiency of our data structure, a road network of 66,437 roads was used. A set of 443,983 moving objects was randomly positioned on edges of the planar graph, with location updates made over 5, 50 and 100 time steps. This resulted in 3.2 x 10[superscript 6], 32 x 10[superscript 6] and 64 x 10[superscript 6] location updates, respectively, indexed by the data structures. Average search times for random queries to find moving objects indexed by a GStree were compared to average search times for the same queries on moving objects indexed by a MON-tree. Results indicate that the GStree is up to 24 times faster than the MON-tree for internal memory searching, and visits between 3.6 and 38 times fewer nodes. Analysis indicates the GStree will be significantly faster for external memory search where the search time is dominated by the number of disk I/Os.
Graph Strip Tree for Efficient Search of Objects Moving on a Graph
(2010) Le, Thuy, T.; Nickerson, Bradford, G.
A spatio-temporal data structure to index objects moving at constant velocity on a graph is presented. It is designed to efficiently answer rectangle R plus time instance and time interval queries about the past positions of moving objects. Such data structures are useful, for example, when searching for vehicles moving on a road network in specific areas at specif times. Unlike other data structures that use Rtrees to index bounding boxes of moving object trajectories, our data structure represents moving objects as lines in a bounded space. For n moving object instances (unique entries of moving objects) on a graph with |E| edges, we show that O(log2 |E| + |L| x log2(n/|E|) + k) time is required to answer a rectangle R plus time interval query, for |L| the number of edges intersected by R and k the number of moving objects in range. Space O(n + k + |E|) is required to store n moving object instances with k intersections among them in |E| ordered polyline trees. Space Ω(n + |E|) is required to store the history of all n moving object instances.
k-d Range Search with Binary Patricia Tries
(2005) Shi, Qingxiu; Nickerson, Bradford, G.
We use Patricia tries to represent textual and spatial data, and present a range search algorithm for reporting all k-d records from a set of size n intersecting a query rectangle. Data and queries include both textual and spatial data. Patricia tries are evaluated experimentally (for n up to 1,000,000) using uniform distributed random spatial data and textual data selected from the Canadian toponymy. We compared the performance of the Patricia trie for k-d points, k-d rectangles and k-d combined textual and spatial data to the k-d tree, R*-tree, Ternary Search Trie and the naive method. Overall, our experiments show that Patricia tries are the best when F Є [0, log2 n] (F is the number of data in range). The expected range search time for Patricia tries was determined theoretically, and found to agree with experimental results when 2 <= k <= 20.
k-dimensional orthogonal range search with tries
(2002) Nickerson, Bradford, G.; Bu, Lingke
We present an algorithm using tries to solve the orthogonal range search problem on k dimensions. The algorithm reports all k-d hyper-rectangles intersecting a k-d axis-aligned query hyper-rectangle W, and supports dynamic operations. For the input data set D and W drawn from a uniform, random distribution, we analyse the expected time for orthogonal range search. We show that the storage S(n, k) =O(nk), and the expected preprocessing time P(n, k) = O(nk) for a trie containing n k-d hyper-rectangles.
MOSAA developer's guide
(1996) Wang, Jin; Nickerson, Bradford, G.; Lees, Ronald, M.
MOSAA (Molecular Spectroscopic Assignment Assistant) is a knowledge-based system that can assist physicists in spectroscopic assignment. This guide presents the MOSAA system from a developer's view-point. It gives the rule grammar as well as descriptions of rule structure and components associated with it. The inference engine is briefly described using diagrams. Some examples are provided to help the developer understand 'how' to modify or expand the rule base in simple cases. Also, the process of recompiling MOSAA is discussed. A pointer to the source code files is also provided.
On k-d Range Search With Large k
(2006) Shi, Qingxiu; Nickerson, Bradford, G.
We present two new k-dimensional data structures, called the PKD-tree and the PKD[superscript +]-tree, respectively. They are explored for indexing combined text and point data, and evaluated experimentally for orthogonal range search (for 2 < k < 100 and n up to 1,000,000) using synthetic data and real data. We compared the range search performance of the PKD-tree with the PKD[superscript +]-tree, the k-d tree, the Pyramid technique, the R*-tree and naive search. The experimental results show that the PKDtree and the PKD+-tree have very good performance for large k, and they always outperform the Pyramid technique, and are better than k-d tree and the R*-tree when k > log[subscript 2]n. For a PKD+-tree built from n uniform and random data points, an orthogonal range search with a query square W of side length ^ visits O(k log n + n(1 - (1 - 2^)[superscript k])) nodes for ^ < 0.5.
On the equivalence of B-trees and deterministic skip list
(1996) Lamoureux, Michael, G.; Nickerson, Bradford, G.
In this paper we show the functional and structural equivalence of B-trees and deterministic skip lists by defining two new B-tree structures, the Bd-tree and Bd[superscript +] -tree, which we use to provide an explicit mapping between deterministic skip lists (DSLs) and B-trees. This mapping is invertible and formalizes the correspondence that exists between the structures, allowing us to prove the equivalence of B-tree and deterministic skip list data structures. This result is important for a number of reasons. It validates the use of deterministic skip lists as index structures while allowing one to determine the relationship of deterministic skip lists to other balanced search tree structures. This equivalence provides further insight into a comparison of the 1-3 deterministic skip list to the red-black tree and to the 1-d range tree. We now know that we can interchange between the red-black tree and the 1-3 DSL and that the dynamic 1-d range tree and 1-3 DSL are equivalent structures. Keywords: B-trees, deterministic skip lists, equivalent data structures, balanced search tree structures, Bd-trees, Bd[superscript +]-trees
Optimal Space Data Structures for I/O Efficient Search of Objects Moving on a Graph
(2009) Le, Thuy, T., T.; Nickerson, Bradford, G.
We present a space optimal spatio-temporal data structure called minimum I/O Graph Strip Tree (minGStree) to index objects assumed to move at constant velocity on the edges of a graph. The minGStree is designed to efficiently answer time instance and time interval queries about the past positions of moving objects. The minGStree uses O(n/B) blocks of external memory, where n is the number of moving object instances (unique entries of moving objects) and B is the I/O block size. We propose two variations of the minGStree: minGStreeI and minGStreeR. For n moving object instances distributed in a uniform fashion on the E edges of a graph over a time domain [0; T], the expected number of I/Os required to determine the moving objects intersecting one edge (for both time instance queries and time interval queries) in a minGStreeI is O(logB(n/E)+k). In the minGStreeR variation, O(n/E + k[superscript ''']) I/Os are required for the same query. k and k[superscript '''] are the number of disk blocks required to store the time intervals intersecting the time query, and the rectangles intersecting the query, respectively. We anticipate this data structure will be practical to implement.
Sensor web language for dynamic sensor networks
(2010) Saini, Gunita; Nickerson, Bradford, G.
The electronic chart: A report based on a workshop held at the University of New Brunswick 21-23 June 1982
Hamilton, Angus, C.; Nickerson, Bradford, G.
This report is the results of the first “Workshop on the Electronic Chart”. The workshop, held at the University of New Brunswick, Fredericton, from 21 to 23 June 1982, brought together mariners (users), hydrographers (chart producers), marine regulation administrator, and researchers in relevant fields (see ‘Participants’). Although each participant spoke briefly on his area of expertise, much of the time was spent in semi-structured discussion. Sessions were designated for discussion of: Rationale: Why? When? The long term goal (assuming no constraints). Technology review and critique: Hardware/software, potential and limitations (constraints). Non-technical constraints: Legal, regulatory, administrative and financial constraints were all considered. The short term objective. A development scenario. The aim of the workshop was to explore the implications of electronic technology advances on the production and use of the nautical chart. In this report, the authors have tried to incorporate the consensus from the presentations and discussions at the workshop. Much of the detail presented in the technology review session has been included in the appendices, along with additional material provided subsequently by the participants. In mid-July a draft of this report was distributed to all participants for review. On receipt of the reviews, considerable re-structuring of the report was done, but no significant changes were made in the executive summary or in the conclusions. Having followed this procedure, the authors are confident that the significant statements and conclusions presented here are a valid consensus of the discussions. The Electronic Chart Workshop and preparation of this report were sponsored by the Canadian Hydrographic Service, Department of Fisheries and Oceans, Ottawa, through DSS contract serial number 0SC82-000127. Mr. R.M. Eaton was project officer for this contract and, in collaboration with Mr. N.M. Anderson, did the pre-workshop planning. The authors gratefully acknowledge the expertise of Ms Wendy Wells in editing the text and in compiling it on the word processor.
The electronic chart: A report based on a workshop held at the University of New Brunswick 21-23 June 1982
Hamilton, Angus, C.; Nickerson, Bradford, G.
This report is the results of the first “Workshop on the Electronic Chart”. The workshop, held at the University of New Brunswick, Fredericton, from 21 to 23 June 1982, brought together mariners (users), hydrographers (chart producers), marine regulation administrator, and researchers in relevant fields (see ‘Participants’). Although each participant spoke briefly on his area of expertise, much of the time was spent in semi-structured discussion. Sessions were designated for discussion of: Rationale: Why? When? The long term goal (assuming no constraints). Technology review and critique: Hardware/software, potential and limitations (constraints). Non-technical constraints: Legal, regulatory, administrative and financial constraints were all considered. The short term objective. A development scenario. The aim of the workshop was to explore the implications of electronic technology advances on the production and use of the nautical chart. In this report, the authors have tried to incorporate the consensus from the presentations and discussions at the workshop. Much of the detail presented in the technology review session has been included in the appendices, along with additional material provided subsequently by the participants. In mid-July a draft of this report was distributed to all participants for review. On receipt of the reviews, considerable re-structuring of the report was done, but no significant changes were made in the executive summary or in the conclusions. Having followed this procedure, the authors are confident that the significant statements and conclusions presented here are a valid consensus of the discussions. The Electronic Chart Workshop and preparation of this report were sponsored by the Canadian Hydrographic Service, Department of Fisheries and Oceans, Ottawa, through DSS contract serial number 0SC82-000127. Mr. R.M. Eaton was project officer for this contract and, in collaboration with Mr. N.M. Anderson, did the pre-workshop planning. The authors gratefully acknowledge the expertise of Ms Wendy Wells in editing the text and in compiling it on the word processor.

Browsing by Author "Nickerson, Bradford, G."

Results Per Page

Sort Options