Approximate Range Searching in External Memory

In this paper, we present two linear-size external memory data structures for approximate range searching. Our first structure, the BAR-B-tree, stores a set of N points in ℝ ^d and can report all points inside a query range Q by accessing O(log  _B N+ε ^γ +k _ε /B) disk blocks, where B is the disk block size, γ=1−d for convex queries and γ=−d otherwise, and k _ε is the number of points lying within a distance of ε⋅diam (Q) to the query range Q. Our second structure, the object-BAR-B-tree, is able to store objects of arbitrary shapes of constant complexity and provides similar query guarantees. In addition, both structures can support other types of range searching queries such as range aggregation and nearest-neighbor. Finally, we present I/O-efficient algorithms to build these structures.     

Top-k queries on temporal data

The database community has devoted extensive amount of efforts to indexing and querying temporal data in the past decades. However, insufficient amount of attention has been paid to temporal ranking queries. More precisely, given any time instance t, the query asks for the top-k objects at time t with respect to some score attribute. Some generic indexing structures based on R-trees do support ranking queries on temporal data, but as they are not tailored for such queries, the performance is far from satisfactory. We present the Seb-tree, a simple indexing scheme that supports temporal ranking queries much more efficiently. The Seb-tree answers a top-k query for any time instance t in the optimal number of I/Os in expectation, namely, O(log_B \fracNB+\frackB){O\left({\rm log}_B\,\frac{N}{B}+\frac{k}{B}\right)} I/Os, where N is the size of the data set and B is the disk block size. The index has near-linear size (for constant and reasonable k _max values, where k _max is the maximum value for the possible values of the query parameter k), can be constructed in near-linear time, and also supports insertions and deletions without affecting its query performance guarantee. Most of all, the Seb-tree is especially appealing in practice due to its simplicity as it uses the B-tree as the only building block. Extensive experiments on a number of large data sets, show that the Seb-tree is more than an order of magnitude faster than the R-tree based indexes for temporal ranking queries.     

Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies

In recent years, management of moving objects has emerged as an active topic of spatial access methods. Various data structures （indexes） have been proposed to handle queries of moving points, for example, the well-known B^x-tree uses a novel mapping mechanism to reduce the index update costs. However, almost all the existing indexes for predictive queries are not applicable in certain circumstances when the update frequencies of moving objects become highly variable and when the system needs to balance the performance of updates and queries. In this paper, we introduce two kinds of novel indexes, named B^y-tree and αB^y-tree. By associating a prediction life period with every moving object, the proposed indexes are applicable in the environments with highly variable update frequencies. In addition, the αB^y-tree can balance the performance of updates and queries depending on a balance parameter. Experimental results show that the B^y-tree and αB^y-tree outperform the B^x-tree in various conditions.     

The structure factor of dense two-dimensional polymer solutions

According to the generalized Porod law the intramolecular structure factor F(q) of compact objects with surface dimension ds scales as F(q)/N≈1/(R(N)q)^2d−ds in the intermediate range of the wave vector q with d being the dimension of the embedding space, N the mass of the objects and R(N)∼N1/d their typical size. By means of molecular-dynamics simulations of a bead-spring model with chain lengths up to N=2048 it is shown that dense self-avoiding polymers in strictly two dimensions (d=2) adopt compact configurations of surface dimension ds=5/4. In agreement with the generalized Porod law the Kratky representation of F(q) thus reveals a nonmonotonous behavior with q²F(q)∼1/(N1/2q)^3/4. Using a similar data analysis we argue briefly that melts of non-concatenated rings in three dimensions become marginally compact with ds=d=3, i.e. q²F(q)∼N⁰/q, for asymptotically long chains.     

MOVIES: indexing moving objects by shooting index images

With the exponential growth of moving objects data to the Gigabyte range, it has become critical to develop effective techniques for indexing, updating, and querying these massive data sets. To meet the high update rate as well as low query response time requirements of moving object applications, this paper takes a novel approach in moving object indexing. In our approach, we do not require a sophisticated index structure that needs to be adjusted for each incoming update. Rather, we construct conceptually simple short-lived index images that we only keep for a very short period of time (sub-seconds) in main memory. As a consequence, the resulting technique MOVIES supports at the same time high query rates and high update rates, trading this property for query result staleness. Moreover, MOVIES is the first main memory method supporting time-parameterized predictive queries. To support this feature, we present two algorithms: non-predictive MOVIES and predictive MOVIES. We obtain the surprising result that a predictive indexing approach—considered state-of-the-art in an external-memory scenario—does not scale well in a main memory environment. In fact, our results show that MOVIES outperforms state-of-the-art moving object indexes such as a main-memory adapted B ^x -tree by orders of magnitude w.r.t. update rates and query rates. In our experimental evaluation, we index the complete road network of Germany consisting of 40,000,000 road segments and 38,000,000 nodes. We scale our workload up to 100,000,000 moving objects, 58,000,000 updates per second and 10,000 queries per second, a scenario at a scale unmatched by any previous work.     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

Nearest and reverse nearest neighbor queries for moving objects

With the continued proliferation of wireless communications and advances in positioning technologies, algorithms for efficiently answering queries about large populations of moving objects are gaining interest. This paper proposes algorithms for k nearest and reverse k nearest neighbor queries on the current and anticipated future positions of points moving continuously in the plane. The former type of query returns k objects nearest to a query object for each time point during a time interval, while the latter returns the objects that have a specified query object as one of their k closest neighbors, again for each time point during a time interval. In addition, algorithms for so-called persistent and continuous variants of these queries are provided. The algorithms are based on the indexing of object positions represented as linear functions of time. The results of empirical performance experiments are reported.     

Efficient temporal counting with bounded error

This paper studies aggregate search in transaction time databases. Specifically, each object in such a database can be modeled as a horizontal segment, whose y-projection is its search key, and its x-projection represents the period when the key was valid in history. Given a query timestamp q _t and a key range , a count-query retrieves the number of objects that are alive at q _t , and their keys fall in . We provide a method that accurately answers such queries, with error less than , where N _alive(q _t ) is the number of objects alive at time q _t , and ɛ is any constant in (0, 1]. Denoting the disk page size as B, and n =  N / B, our technique requires O(n) space, processes any query in O(log _B n) time, and supports each update in O(log _B n) amortized I/Os. As demonstrated by extensive experiments, the proposed solutions guarantee query results with extremely high precision (median relative error below 5%), while consuming only a fraction of the space occupied by the existing approaches that promise precise results.     

A new quantum claw-finding algorithm for three functions

Fork functionsf ₁, ...f _k, ak-tuple (x ₁, ...x _k) such thatf ₁(x ₁)=...=f _k(x _k) is called a claw off ₁, ...,f _k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the numberM of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requiresO(N ^7/8 logN) queries to find a claw, but our algorithm requiresO(N ^3/4 logN) queries ifM ≤ √N andO(N ^7/12 M ^1/3 logN) queries otherwise. Thus, our algorithm is more efficient ifM≤N ^7/8. Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Akinori Kawachi: Received B.Eng. and M.Info. from Kyoto University in 2000 and 2002, respectively. His research interests are quantum computation and distributed computation.     

A taxonomy for moving object queries in spatial databases

In the past decade, many works have focused on the development of moving object database indexing and querying. Most of those works have concentrated on the common spatial queries which are used with static objects as well. However, moving objects have different features from static objects which may lead to a variety of queries. Therefore, it is important to understand the full spectrum of moving object queries, even before starting to build an index structure for such objects. The aim of this paper is to provide a complete picture of the capabilities of moving object queries. Thus motivated, in this paper we propose a taxonomy of moving object queries, comprising five perspectives: (i) Location perspective, (ii) Motion perspective, (iii) Object perspective, (vi) Temporal perspective and (v) Patterns perspective. These give an overall view of what moving object queries are about. In this work, each perspective is described and examples are given.     

Indexing in-network trajectory flows

Indexing moving objects (MO) is a hot topic in the field of moving objects databases since many years. An impressive number of access methods have been proposed to optimize the processing of MO-related queries. Several methods have focused on spatio-temporal range queries, which represent the foundation of MO trajectory queries. Surprisingly, only a few of them consider that the objects movements are constrained. This is an important aspect for several reasons ranging from better capturing the relationship between the trajectory and the network space to more accurate trajectory representation with lower storage requirements. In this paper, we propose T-PARINET, an access method to efficiently retrieve the trajectories of objects moving in networks. T-PARINET is designed for continuous indexing of trajectory data flows. The cornerstone of T-PARINET is PARINET, an efficient index for historical trajectory data. The structure of PARINET is based on a combination of graph partitioning and a set of composite B⁺-tree local indexes. Because the network can be modeled using graphs, the partitioning of the trajectory data makes use of graph partitioning theory and can be tuned for a given query load and a given data distribution in the network space. The tuning process is built on a good quality cost model that is supplied with PARINET. The advantage of having a cost model is twofold; it allows a better integration of the index into the query optimizer of any DBMS, and it permits tuning the index structure for better performance. The tuning process can be performed before the index creation in the case of historical data or online in the case of indexing data flows. In fact, massive online updates can degrade the index quality, which can be measured by the cost model. We propose a specific maintenance process that results into T-PARINET. We study different types of queries and provide an optimized configuration for several scenarios. T-PARINET can easily be integrated into any RDBMS, which is an essential asset particularly for industrial or commercial applications. The experimental evaluation under an off-the-shelf DBMS shows that our method is robust. It also significantly outperforms the reference R-tree-based access methods for in-network trajectory databases.     

Quantum Separation of Local Search and Fixed Point Computation

We give a lower bound of Ω(n ^(d−1)/2) on the quantum query complexity for finding a fixed point of a discrete Brouwer function over grid [n] ^d . Our lower bound is nearly tight, as Grover Search can be used to find a fixed point with O(n ^d/2) quantum queries. Our result establishes a nearly tight bound for the computation of d-dimensional approximate Brouwer fixed points defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. It can be extended to the quantum model for Sperner’s Lemma in any dimensions: The quantum query complexity of finding a panchromatic cell in a Sperner coloring of a triangulation of a d-dimensional simplex with n ^d cells is Ω(n ^(d−1)/2). For d=2, this result improves the bound of Ω(n ^1/4) of Friedl, Ivanyos, Santha, and Verhoeven. More significantly, our result provides a quantum separation of local search and fixed point computation over [n] ^d , for d≥4. Aaronson’s local search algorithm for grid [n] ^d , using Aldous Sampling and Grover Search, makes O(n ^d/3) quantum queries. Thus, the quantum query model over [n] ^d for d≥4 strictly separates these two fundamental search problems.     

Dynamic multi-dimensional data structures based on quad- and k—d trees

Summary Quad-trees and k—d trees have been noted for their lack of dynamic properties as data structures for multi-dimensional point sets. We describe a method to insert points in a quad-tree while keeping the tree balanced that achieves an average time complexity of O(log² N) per insertion, where N is the number of updates performed on the quad-tree. We define a structure similar to a quad-tree, called a pseudo quad-tree, and show how it can be used to handle both insertions and deletions in O(log² N) average time. We also discuss how quad-trees and pseudo quadtrees can be extended for use in configurations of points in which more than one point may have a same value in some equal coordinate, without altering the earlier time bounds for insertions, deletions and queries. Similar algorithms are given for k—d trees and the same average time bounds for insertion and deletion are achieved.The work of this author was partially supported by the Netherlands Organization for the Advancement of Pure Research (ZWO).     

Direction-aware KNN queries for moving objects in a road network

Recently more and more people focus on k-nearest neighbor (KNN) query processing over moving objects in road networks, e.g., taxi hailing and ride sharing. However, as far as we know, the existing k-nearest neighbor (KNN) queries take distance as the major criteria for nearest neighbor objects, even without taking direction into consideration. The main issue with existing methods is that moving objects change their locations and directions frequently over time, so the information updates cannot be processed in time and they run the risk of retrieving the incorrect KNN results. They may fail to meet users’ needs in certain scenarios, especially in the case of querying k-nearest neighbors for moving objects in a road network. In order to find the top k-nearest objects moving toward a query point, this paper presents a novel algorithm for direction-aware KNN (DAKNN) queries for moving objects in a road network. In this method, R-tree and simple grid are firstly used as the underlying index structure, where the R-tree is used for indexing the static road network and the simple grid is used for indexing the moving objects. Then, it introduces the notion of “azimuth” to represent the moving direction of objects in a road network, and presents a novel local network expansion method to quickly judge the direction of the moving objects. By considering whether a moving object is moving farther away from or getting closer to a query point, the object that is definitely not in the KNN result set is effectively excluded. Thus, we can reduce the communication cost, meanwhile simplify the computation of moving direction between moving objects and query point. Comprehensive experiments are conducted and the results show that our algorithm can achieve real-time and efficient queries in retrieving objects moving toward query point in a road network.

     

Geometry Helps in Bottleneck Matching and Related Problems

Let A and B be two sets of n objects in \reals ^d , and let Match be a (one-to-one) matching between A and B . Let min(Match ), max(Match ), and Σ(Match) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of Match , respectively. Bottleneck matching— a matching that minimizes max(Match )— is suggested as a convenient way for measuring the resemblance between A and B . Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is roughly O(n ^1.5 ) . For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n ^1.5 log n ) . A semidynamic data structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion is considered. When A and B are point-sets in the plane, an O(n ⁵ log n) -time algorithm for determining whether for some translated copy the resemblance gets below a given ρ is presented, thus improving the previous result of Alt, Mehlhorn, Wagener, and Welzl by a factor of almost n . This result is used to compute the smallest such ρ in time O(n ⁵ log ² n ) , and an efficient approximation scheme for this problem is also given. The uniform matching problem (also called the balanced assignment problem, or the fair matching problem) is to find Match ^* _U , a matching that minimizes max (Match)-min(Match) . A minimum deviation matching Match ^* _D is a matching that minimizes (1/n)Σ(Match) - min(Match) . Algorithms for computing Match ^* _U and Match ^* _D in roughly O(n ^10/3 ) time are presented. These algorithms are more efficient than the previous O(n ⁴ ) -time algorithms of Martello, Pulleyblank, Toth, and de Werra, and of Gupta and Punnen, who studied these problems for general bipartite graphs. Received October 21, 1997; revised July 16, 1998.     

A Modified Fourier–Galerkin Method for the Poisson and Helmholtz Equations

In this paper we present a modified Fourier–Galerkin method for the numerical solution of the Poisson and Helmholtz equations in a d-dimensional box. The inversion of the differential operators requires O(N ^d ) operations, where N ^d is the number of unknowns. The total cost of the presented algorithms is O(N ^d :log₂:N), due to the application of the Fast Fourier Transform (FFT) at the preprocessing stage. The method is based on an extension of the Fourier spaces by adding appropriate functions. Utilizing suitable bilinear forms, approximate projections onto these extended spaces give rapidly converging and highly accurate series expansions.     

Processing moving queries over moving objects using motion-adaptive indexes

This paper describes a motion-adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Furthermore, we introduce the concepts of guaranteed safe radius and optimistic safe radius to extend our motion-adaptive indexing scheme to evaluating moving continual k-nearest neighbor (kNN) queries. Our experiments show that the proposed motion-adaptive indexing scheme is efficient for the evaluation of both moving continual range queries and moving continual kNN queries.     

Stochastic adaptive pole-zero assignment with convergence analysis

The adaptive control u_n is designed for the stochastic system A(z)y_n+1 = B(z)u_n+C(z)w_n+1 with unknown constant matrix coefficients in the polynomials A(z), B(z) and C(z) in the shift-back operator with the purposes that (1) the unknown matrices are strongly consistently estimated and (2) the poles and zeros are replaced in such a way that the system itself is transferred to A⁰(z)y_n+1 = B⁰(z)u_n⁰+_n+1 with given A⁰(z), B⁰(z) and u_n⁰ so that the pole-zero assignment error {_n+1} is minimized. The problem of adaptive pole-zero assignment combined with tracking is also considered in this paper. Conditions used are imposed only on A(z), B(z) and C(z).     

Qualitative relations between moving objects in a network changing its topological relations

The Qualitative Trajectory Calculus on Networks (QTC_N) defines qualitative relations between two continuously moving point objects (MPOs) moving along a network. As prevailing in other research, this network is presumed static in QTC_N. Actually, in many cases, networks are dynamic entities. For example in a road network, the opening of a bridge can temporarily close the connection between two junctions; traffic jams and traffic lights increase the time needed to travel from A to B. Therefore, it is interesting to examine what happens with qualitative relations between two continuously moving point objects if there are changes in the network. In this paper, we introduce QTC_DN^′, being the Qualitative Trajectory Calculus on Changing Networks able to handle topological network changes. Potential applications of the calculus in transportation are highlighted, clearly illustrating the usefulness of the calculus.