Similarity search in semialgebraic pattern spaces

Similaritiy Search in Semialgebraic Pattern Spaces (Extended Abstract) Christian Knauer a aInstitut f¨ur Informatik, Freie Universit¨at Berlin, Takustraße 9, D-14195 Berlin, Germany Abstract We describe a general technique to construct data structures for similarity search in semialgebraic pattern spaces. These spaces capture most known combinations of geometric patterns (e.g., point sets, polygons, polygonal curves) and geometric distance measures for them (e.g. Hausdorff-distance, area of overlap, Fr´echet-distance) together with their quotients under various transformation classes (e.g., translations, rigid motions) and they provide the first non-trivial exact search structures in these settings. Key words: Computational geometry, Shape matching, Similarity queries, Data structures 1. Introduction Similarity search is a much-studied and practically important type of problem: Given a set D of npatterns from a suitable class of valid geometric patterns (e.g., polygonal curves), preprocess them in such a way that we can determine quickly for a query pattern Q, which of the npreprocessed patterns is most similar to the query object (this is called a similarity query). We assume that we have an appropriate distance measure δ(e.g., the smallest Fr´echet distance that can be achieved under translations) to asses the similarity of two patterns. Satisfactory algorithmic results exist only in the case that the patterns can be encoded in a Euclidean space, or an L1- or L∞-space such that δis the corresponding metric [9], or in the case that they can be embedded in such spaces with a low distortion [7,6]. Then we have available the very powerful techniques of Voronoi decompositions. Some algorithms were formulated with ‘vantage points’ or similar devices [2,3,5,10], but then there are no general performance bounds: only under additional assumptions that enforce in some way that the distance measure is a metric that is Email address: [email protected] (Christian Knauer). ‘similar’ to a Euclidean metric it is possible to obtain nontrivial bound on the performance of these algorithms [9]. In this paper, we study the case where the size of the individual patterns is small, compared to n. To be more precise, we assume that |I|=O(1) for all I∈ D. In that case the distances δ(Q, I), can be computed in O(1) time (for reasonable δ). So the query can be answered in O(n) time without additional storage and preprocessing, but up to now there are no algorithms and data structures that allow such queries with a nontrivial query time among preprocessed pattern sets. We describe a general technique to construct data structures for similarity queries for many combinations of geometric patterns (e.g., point sets, polygons, polygonal curves) and geometric distance measures (e.g. Hausdorff-distance, area of overlap, Fr´echetdistance) together with their quotients under various transformation classes (e.g., translations, rigid motions). The solution achieves sublinear query time with quadratic preprocessing time and storage and provides the first non-trivial search structures in these settings. Apattern space Π = (Ω, δ) of dimension dis a set of geometric objects Ω, where each object can be described by exactly dreal parameters, together with a distance measure δthat maps pairs of objects to non-negative real numbers. Usually 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry we identify Ω with Rd, the parameter space of Π. The objects in Ω are called patterns. Intuitively, when δ(P, I) is small, we consider the patterns P and Ito be similar. Note that we do not demand that δhas some special properties (like being a metric, etc.). As an example consider polygonal chains in the plane with at most rvertices and the Fr´echet-distance as a distance measure. Each such chain can be encoded by a sequence of at most 2r real numbers, the coordinates of the vertices of the chain. If a chain has less than rvertices we can simply pad this description by repeating the last vertex; note that this padding does not interfere with the distance function. A pattern space Π = (Rd, δ) is called semialgebraic, if the set FΠ:= {(P, I, ǫ)∈Rd×Rd×R| δ(P, I)≤ǫ}is semialgebraic, i.e., there is a boolean formula Bin sboolean variables z1, . . . , zs, and there are spolynomials g1,...,gsin (2d+ 1) real variables xP,xI, xǫ(xPand xIare actually sequences of dvariables each), such that δ(P, I)≤ǫ⇐⇒ B(z1←[g1(xP←P, xI←I, xǫ←ǫ)≥0], ... zs←[gs(xP←P, xI←I, xǫ←ǫ)≥0]) is true (←denotes variable substitution and [X] is the truth value of the predicate X). As an example consider the set of all point sets in the plane with at most rpoints each and the directed Hausdorff-distance as a distance measure. Recall that for compact sets P, I ⊆Rdthe directed Hausdorff distance from Pto I, is defined as h(P, I) := maxx∈Pminy∈I||x−y||. This is a pattern space of dimension 2r, since each pattern Pcan be encoded by a sequence of at most 2rreal numbers, the coordinates of the points in P. If Phas less than rpoints we can simply pad this description by repeating some point; note that this padding does not interfere with the distance function. To see that it is actually a semialgebraic pattern space, note that for two finite point sets P, Iand ǫ > 0 we have that h(P, I)≤ǫ⇐⇒ ∀p∈P∃i∈I:||p−i||2−ǫ2≤0 ⇐⇒ ^ p∈P ∃i∈I:||p−i||2−ǫ2≤0 ⇐⇒ ^ p∈P _ i∈I ||p−i||2−ǫ2≤0. We will see in Section 3 that the notion of a semialgebraic pattern space captures most known combinations of geometric patterns (e.g., point sets, polygons, polygonal curves) and geometric distance measures (e.g. Hausdorff-distance, area of overlap, Fr´echet-distance) together with their quotients under various transformation classes. In this paper, we study the problem of similarity search among patterns from a semialgebraic pattern space where the size of the individual patterns is small, compared to their number: Given a data set Dthat consists of npatterns from a semialgebraic pattern space Π = (Ω, δ)of dimension d, where dis constant, preprocess Dinto a data structure to answer the following kind of similarity queries: For a query pattern Q∈Ω, determine –∆(Q, D) := minargI∈D δ(Q, I), the set of patterns in Dto which Qhas the smallest possible distance, and –∆(D, Q) := minargI∈D δ(I, Q), the set of patterns in Dthat have the smallest possible distance to Q. Since dis constant, the distances δ(Q, I), can be computed in O(1) time (for reasonable δ). So these queries can be answered in O(n+k) time (where k is the size of the answer) without additional storage and preprocessing, but up to now there are no algorithms and data structures that allow such queries with a nontrivial query time among preprocessed pattern sets. We will also consider the decision version of the similarity queries, called ǫ-similarity queries, where we are given an additional parameter ǫ > 0, and we want to determine – ∆(Q, D, ǫ) := {I∈ D | δ(Q, I)≤ǫ}, the set of patterns in Dto which Qhas distance at most ǫ, and – ∆(D, Q, ǫ) := {I∈ D | δ(I, Q)≤ǫ}, the set of patterns in Dthat have distance at most ǫto Q. Again the brute-force approach can answer these queries in O(n+k) time, but there are no data structures that allow such queries with a nontrivial query time among preprocessed pattern sets. 2. Similaritiy queries in pattern spaces In this abstract we only consider the decision version of the similarity queries. We describe a data structure that answers ∆(Q, D, ǫ)-queries (the case March 25-26, 2004 Seville (Spain) of ∆(D, Q, ǫ)-queries is completely symmetric). The same techniques apply to similarity queries as well and yield similar results. Our main result is the following Theorem 1 Suppose we are given a set Dthat consists of npatterns from a semialgebraic pattern space Πof dimension d=O(1). Then we can build in O(n2)time a data structure of size O(n2)that answers ǫ-similarity queries in O(n1−1/(2d−3) +k) time, where kis the size of the answer. PROOF. The construction works in two steps. We first describe a data structure that can be built in O(n2d−2) time (and requires the same amount of space) and can answer a query in O(log n+k) time, where kis the size of the answer. Then we use a simple partitioning approach to yield the desired result (in fact we prove a somewhat stronger tradeoff that implies the Theorem). Since Π = (Ω, δ) is a semialgebraic pattern space of dimension d=O(1), there is a boolean formula Bin s=O(1) boolean variables z1, . . . , zs, and there are spolynomials g1,...,gsin (2d+ 1) real variables xP,xI, xǫ, such that δ(Q, I)≤ǫ⇐⇒ B(z1←[g1(xQ←Q, xI←I, xǫ←ǫ)≥0], ... zt←[gt(xQ←Q, xI←I, xǫ←ǫ)≥0]). For j= 1,...,sand for all I∈ D, we compute the (d+ 1)-variate polynomials gj,I(xQ, xǫ) := gj(xQ,xI←I, xǫ). This is done by substituting Ifor xIin gjand therefore takes time O(1). The total time to compute all these polynomials is O(n). For the gj,I we compute a subdivision Ξ of Rd+1 with the property that the sign of each gj,I remains constant on each cell of the subdivision. Such a subdivsion of size O(n2d−3) can be computed in O(n2d−3) time, along with a point-location datastructure L(Ξ) for the subdivision with O(log n) query-time, c.f., [8]; the computation also yields for each cell χ∈Ξ a point (Qχ, ǫχ)∈χ. In a next step we process each cell χ∈Ξ in turn and compute a set Dχ⊂ D, which is initially empty. For all I∈ D we do the following: First compute for j= 1,...,sthe numbers γi,I,χ := gj,I(xQ←Qχ, xǫ←ǫχ). Next, we compute the truth-value BI,χ := B(z1←[γ1,I,χ ≥0],...,zs←[γs,I,χ ≥0]). If BI,χ is true, we have that δ(Qχ, I)≤ǫχand we add Ito Dχ. We augment the data-structure L(Ξ) by storing the set Dχfor each cell χ∈Ξ. The total time needed to compute it is O(n2d−2), and it needs O(n2d−2) space. To answer a query (Q, ǫ)∈Ω×R, we proceed as follows: Using L(Ξ) we locate the cell χ∈Ξ with (Q, ǫ)∈χin O(log n) time. Since the sign of the gj,I’s is constant on each cell of Ξ, we have that δ(Qχ, I)≤ǫχiff δ(Q, I)≤ǫ, so we can report Dχ as the answer to the query. The total time required is O(log n+k), where k=|Dχ|is the size of the answer. Now we use a simple partitioning approach to yield the desired result: We split Dinto g= Θ(n/m) groups D1,...,Dg, each of size Θ(m), where 1 ≤m≤nis a suitable parameter (see below). Then we build the aforementioned datastructure for each Diseparately. To answer a query (Q, ǫ)∈Ω×R, we query each data-structure separately and combine the individual answers. The total time needed to compute all the structures is O(gm2d−2) = O(nm2d−3) (this is also the total space requirement), and the query time is O(glog n) = O((n/m) log n). Setting m= n1/(2d−3) proves the claimed result. ✷ 3. More semialgebraic pattern spaces In the following we show that the notion of a semialgebraic pattern space captures many combinations of geometric patterns (e.g., point sets, polygons, polygonal curves) and geometric distance measures (e.g., Hausdorff-distance, area of overlap, Fr´echet-distance) together with their quotients under various transformation classes (e.g., translations, rigid motions). Since the set accepted by an algebraic decision tree is semialgebraic we get the following Lemma 2 Let Πbe a pattern space. If FΠcan be decided by an algorithm in the algebraic decision tree model, then Πis semialgebraic. It is straightforward to verify that many of the algorithms for deciding the most prominent distance measures can be implemented in the algebraic decision tree model, c.f., [1]. This shows for example that polygonal curves on kvertices in Rd 20th European Workshop on Computational Geometry wrt. the Fr´echet-distance constitute a semialgebraic pattern space. Let Π = (Rd, δ) be a semialgebraic pattern space, and let t:Rd×Rd×Rf→Rd×Rdbe a function. This function induces a new distance measure and thus a new pattern space Πt:= (Rd, δt) as follows: δt(P, I) := min v∈Rfδ(t(P, I, v)). We call δtthe quotient of δunder tand fthe number of degrees of freedom of t. As an example consider again the pattern space of all point sets in the plane with at most rpoints each and the directed Hausdorff-distance h(,) as a distance measure. The function t(P, I, v) := (P+ v, I) has two degrees of freedom and we have that ht(P, I) = minv∈R2h(P+v, I) is the smallest directed Hausdorff distance that a translate of Phas to I. Theorem 3 If tis rational, then Πtis semialgebraic. In that case a semialgebraic description of FΠtcan effectilvey be computed from such a description of FΠ. PROOF. First, observe that δt(Q, I)≤ǫ⇐⇒ ∃v∈Rf:δ(t(Q, I, v)) ≤ǫ. Since Π = (Ω, δ) is a semialgebraic pattern space and tis rational, there is a boolean formula B in sboolean variables z1,...,zs, and there are s polynomials g1,...,gsin (2d+ 1) real variables xP,xI, xǫ, such that δt(Q, I)≤ǫ⇐⇒ ∃vB(z1←[g1(t(xQ←Q, xI←I, xv←v), xǫ←ǫ)≥0], ... zs←[gs(t(xQ←Q, xI←I, xv←v), xǫ←ǫ)≥0] (xvis a sequence of fnew variables). In general gi(t(),) is not a polynomial. However, since tis rational, the conditions ’gi(t(),)≥0’ can be rewritten as equivalent polynomial inequalities. This shows that FΠtis a Tarski-set, and therefore semialgebraic. Using standard quantifier elimination techniques [4], a semialgebraic description of FΠtcan effectilvey be computed. ✷ If the dimension dof Π is O(1) (relative to n= |D|), then the dimension d′of Πtis also O(1) (unfortunately, in general, d′is doubly exponential in d) and a semialgebraic description of FΠtcan be computed in O(1) time. This shows for example that polygonal curves on kvertices in Rdwrt. the smallest Fr´echet-distance that can be attained under rigid motions constitute a semialgebraic pattern space of dimension O(1) if k, d =O(1). Acknowledgments. The author would like to thank Peter Braß for fruitful discussion on the subject. References [1] H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 121–153. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000. [2] S. Brin. Near neighbor search in large metric spaces. In The VLDB Journal, pages 574–584, 1995. [3] K. L. Clarkson. Nearest neighbor queries in metric spaces. In Proc. 29th Annu. ACM Sympos. Theory Comput., pages 609–617, 1997. [4] G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Proc. 2nd GI Conference on Automata Theory and Formal Languages, volume 33 of Lecture Notes Comput. Sci., pages 134–183. Springer-Verlag, 1975. [5] E.Ch´avez, G. Navarro, R.Baeza- Yates, and J.Marroqu´ın. Searching in metric spaces. Technical Report TR/DCC-99-3, Dept. of Computer Science, Univ. of Chile, 1999. [6] P. Indyk. Approximate nearest neighbor algorithms for frechet distance via product metrics. In Proceedings of the eighteenth annual symposium on Computational geometry, pages 102–106. ACM Press, 2002. [7] P. Indyk and M. Farach-Colton. Approximate nearest neighbor algorithms for Hausdorff metrics via embeddings. In Proc. 40th Annu. IEEE Sympos. Found. Comput. Sci., pages 171–180, 1999. [8] V. Koltun. Almost tight upper bounds for vertical decompositions in four dimensions. In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., 2001. [9] S. A. Nene and S. K. Nayar. A simple algorithm for nearest neighbor search in high dimensions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19:989–1003, 1997. [10] P. N. Yianilos. Excluded middle vantage point forests for nearest neighbor search. Technical report, NEC Research Institute, 1999.