Similarity search in semialgebraic pattern spaces

Simila i iy Sea ch in Semialgeb aic Pa e n Spaces (Ex ended Abs ac ) Ch is ian Knaue a aIns i u ¨u In o ma ik, F eie Uni e si ¨a Be lin, Takus aße 9, D-14195 Be lin, Ge many Abs ac We desc ibe a gene al echnique o cons uc da a s uc u es o simila i y sea ch in semialgeb aic pa e n spaces. These spaces cap u e mos known combina ions o geome ic pa e ns (e.g., poin se s, polygons, polygonal cu es) and geome ic dis ance measu es o hem (e.g. Hausdo -dis ance, a ea o o e lap, F ´eche -dis ance) oge he wi h hei quo ien s unde a ious ans o ma ion classes (e.g., ansla ions, igid mo ions) and hey p o ide he i s non- i ial exac sea ch s uc u es in hese se ings. Key wo ds: Compu a ional geome y, Shape ma ching, Simila i y que ies, Da a s uc u es 1. In oduc ion Simila i y sea ch is a much-s udied and p ac i- cally impo an ype o p oblem: Gi en a se D o npa e ns om a sui able class o alid geo- me ic pa e ns (e.g., polygonal cu es), p ep ocess hem in such a way ha we can de e mine quickly o a que y pa e n Q, which o he np ep ocessed pa e ns is mos simila o he que y objec ( his is called a simila i y que y). We assume ha we ha e an app op ia e dis ance measu e δ(e.g., he smalles F ´eche dis ance ha can be achie ed un- de ansla ions) o asses he simila i y o wo pa - e ns. Sa is ac o y algo i hmic esul s exis only in he case ha he pa e ns can be encoded in a Eu- clidean space, o an L1- o L∞-space such ha δis he co esponding me ic [9], o in he case ha hey can be embedded in such spaces wi h a low dis o ion [7,6]. Then we ha e a ailable he e y powe ul echniques o Vo onoi decomposi- ions. Some algo i hms we e o mula ed wi h ‘ an- age poin s’ o simila de ices [2,3,5,10], bu hen he e a e no gene al pe o mance bounds: only un- de addi ional assump ions ha en o ce in some way ha he dis ance measu e is a me ic ha is Email add ess: Ch is ian.Knaue @in . u-be lin.de (Ch is ian Knaue ). ‘simila ’ o a Euclidean me ic i is possible o ob- ain non i ial bound on he pe o mance o hese algo i hms [9]. In his pape , we s udy he case whe e he size o he indi idual pa e ns is small, compa ed o n. To be mo e p ecise, we assume ha |I|=O(1) o all I∈ D. In ha case he dis ances δ(Q, I), can be compu ed in O(1) ime ( o easonable δ). So he que y can be answe ed in O(n) ime wi h- ou addi ional s o age and p ep ocessing, bu up o now he e a e no algo i hms and da a s uc u es ha allow such que ies wi h a non i ial que y ime among p ep ocessed pa e n se s. We de- sc ibe a gene al echnique o cons uc da a s uc- u es o simila i y que ies o many combina ions o geome ic pa e ns (e.g., poin se s, polygons, polygonal cu es) and geome ic dis ance measu es (e.g. Hausdo -dis ance, a ea o o e lap, F ´eche - dis ance) oge he wi h hei quo ien s unde a i- ous ans o ma ion classes (e.g., ansla ions, igid mo ions). The solu ion achie es sublinea que y ime wi h quad a ic p ep ocessing ime and s o - age and p o ides he i s non- i ial sea ch s uc- u es in hese se ings. Apa e n space Π = (Ω, δ) o dimension dis a se o geome ic objec s Ω, whe e each objec can be desc ibed by exac ly d eal pa ame e s, o- ge he wi h a dis ance measu e δ ha maps pai s o objec s o non-nega i e eal numbe s. Usually 20 h EWCG Se ille, Spain (2004) 20 h Eu opean Wo kshop on Compu a ional Geome y we iden i y Ω wi h Rd, he pa ame e space o Π. The objec s in Ω a e called pa e ns. In ui i ely, when δ(P, I) is small, we conside he pa e ns P and I o be simila . No e ha we do no demand ha δhas some special p ope ies (like being a me ic, e c.). As an example conside polygonal chains in he plane wi h a mos e ices and he F ´eche -dis ance as a dis ance measu e. Each such chain can be encoded by a sequence o a mos 2 eal numbe s, he coo dina es o he e ices o he chain. I a chain has less han e ices we can simply pad his desc ip ion by epea ing he las e ex; no e ha his padding does no in e e e wi h he dis ance unc ion. A pa e n space Π = (Rd, δ) is called semialge- b aic, i he se FΠ:= {(P, I, ǫ)∈Rd×Rd×R| δ(P, I)≤ǫ}is semialgeb aic, i.e., he e is a boolean o mula Bin sboolean a iables z1, . . . , zs, and he e a e spolynomials g1,...,gsin (2d+ 1) eal a iables xP,xI, xǫ(xPand xIa e ac ually se- quences o d a iables each), such ha δ(P, I)≤ǫ⇐⇒ B(z1←[g1(xP←P, xI←I, xǫ←ǫ)≥0], ... zs←[gs(xP←P, xI←I, xǫ←ǫ)≥0]) is ue (←deno es a iable subs i u ion and [X] is he u h alue o he p edica e X). As an example conside he se o all poin se s in he plane wi h a mos poin s each and he di- ec ed Hausdo -dis ance as a dis ance measu e. Recall ha o compac se s P, I ⊆Rd he di- ec ed Hausdo dis ance om P o I, is de ined as h(P, I) := maxx∈Pminy∈I||x−y||. This is a pa e n space o dimension 2 , since each pa e n Pcan be encoded by a sequence o a mos 2 eal numbe s, he coo dina es o he poin s in P. I Phas less han poin s we can simply pad his desc ip ion by epea ing some poin ; no e ha his padding does no in e e e wi h he dis ance unc ion. To see ha i is ac ually a semialgeb aic pa e n space, no e ha o wo ini e poin se s P, Iand ǫ > 0 we ha e ha 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 Sec ion 3 ha he no ion o a semialgeb aic pa e n space cap u es mos known combina ions o geome ic pa e ns (e.g., poin se s, polygons, polygonal cu es) and geome ic dis ance measu es (e.g. Hausdo -dis ance, a ea o o e lap, F ´eche -dis ance) oge he wi h hei quo- ien s unde a ious ans o ma ion classes. In his pape , we s udy he p oblem o simila i y sea ch among pa e ns om a semialgeb aic pa - e n space whe e he size o he indi idual pa - e ns is small, compa ed o hei numbe : Gi en a da a se D ha consis s o npa e ns om a semi- algeb aic pa e n space Π = (Ω, δ)o dimension d, whe e dis cons an , p ep ocess Din o a da a s uc u e o answe he ollowing kind o simila i y que ies: Fo a que y pa e n Q∈Ω, de e mine –∆(Q, D) := mina gI∈D δ(Q, I), he se o pa - e ns in D o which Qhas he smalles possible dis ance, and –∆(D, Q) := mina gI∈D δ(I, Q), he se o pa - e ns in D ha ha e he smalles possible dis ance o Q. Since dis cons an , he dis ances δ(Q, I), can be compu ed in O(1) ime ( o easonable δ). So hese que ies can be answe ed in O(n+k) ime (whe e k is he size o he answe ) wi hou addi ional s o - age and p ep ocessing, bu up o now he e a e no algo i hms and da a s uc u es ha allow such que ies wi h a non i ial que y ime among p ep o- cessed pa e n se s. We will also conside he decision e sion o he simila i y que ies, called ǫ-simila i y que ies, whe e we a e gi en an addi ional pa ame e ǫ > 0, and we wan o de e mine – ∆(Q, D, ǫ) := {I∈ D | δ(Q, I)≤ǫ}, he se o pa e ns in D o which Qhas dis ance a mos ǫ, and – ∆(D, Q, ǫ) := {I∈ D | δ(I, Q)≤ǫ}, he se o pa e ns in D ha ha e dis ance a mos ǫ o Q. Again he b u e- o ce app oach can answe hese que ies in O(n+k) ime, bu he e a e no da a s uc u es ha allow such que ies wi h a non i ial que y ime among p ep ocessed pa e n se s. 2. Simila i iy que ies in pa e n spaces In his abs ac we only conside he decision e sion o he simila i y que ies. We desc ibe a da a s uc u e ha answe s ∆(Q, D, ǫ)-que ies ( he case Ma ch 25-26, 2004 Se ille (Spain) o ∆(D, Q, ǫ)-que ies is comple ely symme ic). The same echniques apply o simila i y que ies as well and yield simila esul s. Ou main esul is he ollowing Theo em 1 Suppose we a e gi en a se D ha consis s o npa e ns om a semialgeb aic pa e n space Πo dimension d=O(1). Then we can build in O(n2) ime a da a s uc u e o size O(n2) ha answe s ǫ-simila i y que ies in O(n1−1/(2d−3) +k) ime, whe e kis he size o he answe . PROOF. The cons uc ion wo ks in wo s eps. We i s desc ibe a da a s uc u e ha can be buil in O(n2d−2) ime (and equi es he same amoun o space) and can answe a que y in O(log n+k) ime, whe e kis he size o he answe . Then we use a simple pa i ioning app oach o yield he de- si ed esul (in ac we p o e a somewha s onge adeo ha implies he Theo em). Since Π = (Ω, δ) is a semialgeb aic pa e n space o dimension d=O(1), he e is a boolean o mula Bin s=O(1) boolean a iables z1, . . . , zs, and he e a e spolynomials g1,...,gsin (2d+ 1) eal a iables xP,xI, xǫ, such ha δ(Q, I)≤ǫ⇐⇒ B(z1←[g1(xQ←Q, xI←I, xǫ←ǫ)≥0], ... z ←[g (xQ←Q, xI←I, xǫ←ǫ)≥0]). Fo j= 1,...,sand o all I∈ D, we compu e he (d+ 1)- a ia e polynomials gj,I(xQ, xǫ) := gj(xQ,xI←I, xǫ). This is done by subs i u ing I o xIin gjand he e o e akes ime O(1). The o al ime o com- pu e all hese polynomials is O(n). Fo he gj,I we compu e a subdi ision Ξ o Rd+1 wi h he p ope y ha he sign o each gj,I emains cons an on each cell o he subdi ision. Such a subdi sion o size O(n2d−3) can be compu ed in O(n2d−3) ime, along wi h a poin -loca ion da a- s uc u e L(Ξ) o he subdi ision wi h O(log n) que y- ime, c. ., [8]; he compu a ion also yields o each cell χ∈Ξ a poin (Qχ, ǫχ)∈χ. In a nex s ep we p ocess each cell χ∈Ξ in u n and compu e a se Dχ⊂ D, which is ini ially emp y. Fo all I∈ D we do he ollowing: Fi s compu e o j= 1,...,s he numbe s γi,I,χ := gj,I(xQ←Qχ, xǫ←ǫχ). Nex , we compu e he u h- alue BI,χ := B(z1←[γ1,I,χ ≥0],...,zs←[γs,I,χ ≥0]). I BI,χ is ue, we ha e ha δ(Qχ, I)≤ǫχand we add I o Dχ. We augmen he da a-s uc u e L(Ξ) by s o ing he se Dχ o each cell χ∈Ξ. The o al ime needed o compu e i is O(n2d−2), and i needs O(n2d−2) space. To answe a que y (Q, ǫ)∈Ω×R, we p oceed as ollows: Using L(Ξ) we loca e he cell χ∈Ξ wi h (Q, ǫ)∈χin O(log n) ime. Since he sign o he gj,I’s is cons an on each cell o Ξ, we ha e ha δ(Qχ, I)≤ǫχi δ(Q, I)≤ǫ, so we can epo Dχ as he answe o he que y. The o al ime equi ed is O(log n+k), whe e k=|Dχ|is he size o he answe . Now we use a simple pa i ioning app oach o yield he desi ed esul : We spli Din o g= Θ(n/m) g oups D1,...,Dg, each o size Θ(m), whe e 1 ≤m≤nis a sui able pa ame e (see below). Then we build he a o emen ioned da a- s uc u e o each Disepa a ely. To answe a que y (Q, ǫ)∈Ω×R, we que y each da a-s uc u e sepa a ely and combine he indi idual answe s. The o al ime needed o compu e all he s uc- u es is O(gm2d−2) = O(nm2d−3) ( his is also he o al space equi emen ), and he que y ime is O(glog n) = O((n/m) log n). Se ing m= n1/(2d−3) p o es he claimed esul . ✷ 3. Mo e semialgeb aic pa e n spaces In he ollowing we show ha he no ion o a semialgeb aic pa e n space cap u es many com- bina ions o geome ic pa e ns (e.g., poin se s, polygons, polygonal cu es) and geome ic dis- ance measu es (e.g., Hausdo -dis ance, a ea o o e lap, F ´eche -dis ance) oge he wi h hei quo- ien s unde a ious ans o ma ion classes (e.g., ansla ions, igid mo ions). Since he se accep ed by an algeb aic decision ee is semialgeb aic we ge he ollowing Lemma 2 Le Πbe a pa e n space. I FΠcan be decided by an algo i hm in he algeb aic decision ee model, hen Πis semialgeb aic. I is s aigh o wa d o e i y ha many o he algo i hms o deciding he mos p ominen dis- ance measu es can be implemen ed in he alge- b aic decision ee model, c. ., [1]. This shows o example ha polygonal cu es on k e ices in Rd 20 h Eu opean Wo kshop on Compu a ional Geome y w . he F ´eche -dis ance cons i u e a semialge- b aic pa e n space. Le Π = (Rd, δ) be a semialgeb aic pa e n space, and le :Rd×Rd×R →Rd×Rdbe a unc- ion. This unc ion induces a new dis ance mea- su e and hus a new pa e n space Π := (Rd, δ ) as ollows: δ (P, I) := min ∈R δ( (P, I, )). We call δ he quo ien o δunde and he num- be o deg ees o eedom o . As an example conside again he pa e n space o all poin se s in he plane wi h a mos poin s each and he di ec ed Hausdo -dis ance h(,) as a dis ance measu e. The unc ion (P, I, ) := (P+ , I) has wo deg ees o eedom and we ha e ha h (P, I) = min ∈R2h(P+ , I) is he smalles di- ec ed Hausdo dis ance ha a ansla e o Phas o I. Theo em 3 I is a ional, hen Π is semialge- b aic. In ha case a semialgeb aic desc ip ion o FΠ can e ec il ey be compu ed om such a de- sc ip ion o FΠ. PROOF. Fi s , obse e ha δ (Q, I)≤ǫ⇐⇒ ∃ ∈R :δ( (Q, I, )) ≤ǫ. Since Π = (Ω, δ) is a semialgeb aic pa e n space and is a ional, he e is a boolean o mula B in sboolean a iables z1,...,zs, and he e a e s polynomials g1,...,gsin (2d+ 1) eal a iables xP,xI, xǫ, such ha δ (Q, I)≤ǫ⇐⇒ ∃ B(z1←[g1( (xQ←Q, xI←I, x ← ), xǫ←ǫ)≥0], ... zs←[gs( (xQ←Q, xI←I, x ← ), xǫ←ǫ)≥0] (x is a sequence o new a iables). In gene al gi( (),) is no a polynomial. Howe e , since is a ional, he condi ions ’gi( (),)≥0’ can be ew i en as equi alen polynomial inequali ies. This shows ha FΠ is a Ta ski-se , and he e o e semialgeb aic. Using s anda d quan i ie elimina- ion echniques [4], a semialgeb aic desc ip ion o FΠ can e ec il ey be compu ed. ✷ I he dimension do Π is O(1) ( ela i e o n= |D|), hen he dimension d′o Π is also O(1) (un- o una ely, in gene al, d′is doubly exponen ial in d) and a semialgeb aic desc ip ion o FΠ can be compu ed in O(1) ime. This shows o example ha polygonal cu es on k e ices in Rdw . he smalles F ´eche -dis ance ha can be a ained unde igid mo ions cons i u e a semialgeb aic pa e n space o dimension O(1) i k, d =O(1). Acknowledgmen s. The au ho would like o hank Pe e B aß o ui ul discussion on he sub- jec . Re e ences [1] H. Al and L. J. Guibas. Disc e e geome ic shapes: Ma ching, in e pola ion, and app oxima ion. In J.-R. Sack and J. U u ia, edi o s, Handbook o Compu a ional Geome y, pages 121–153. Else ie Science Publishe s B.V. No h-Holland, Ams e dam, 2000. [2] S. B in. Nea neighbo sea ch in la ge me ic spaces. In The VLDB Jou nal, pages 574–584, 1995. [3] K. L. Cla kson. Nea es neighbo que ies in me ic spaces. In P oc. 29 h Annu. ACM Sympos. Theo y Compu ., pages 609–617, 1997. [4] G. E. Collins. Quan i ie elimina ion o eal closed ields by cylind ical algeb aic decomposi ion. In P oc. 2nd GI Con e ence on Au oma a Theo y and Fo mal Languages, olume 33 o Lec u e No es Compu . Sci., pages 134–183. Sp inge -Ve lag, 1975. [5] E.Ch´a ez, G. Na a o, R.Baeza- Ya es, and J.Ma oqu´ın. Sea ching in me ic spaces. Technical Repo TR/DCC-99-3, Dep . o Compu e Science, Uni . o Chile, 1999. [6] P. Indyk. App oxima e nea es neighbo algo i hms o eche dis ance ia p oduc me ics. In P oceedings o he eigh een h annual symposium on Compu a ional geome y, pages 102–106. ACM P ess, 2002. [7] P. Indyk and M. Fa ach-Col on. App oxima e nea es neighbo algo i hms o Hausdo me ics ia embeddings. In P oc. 40 h Annu. IEEE Sympos. Found. Compu . Sci., pages 171–180, 1999. [8] V. Kol un. Almos igh uppe bounds o e ical decomposi ions in ou dimensions. In P oc. 42nd Annu. IEEE Sympos. Found. Compu . Sci., 2001. [9] S. A. Nene and S. K. Naya . A simple algo i hm o nea es neighbo sea ch in high dimensions. IEEE T ansac ions on Pa e n Analysis and Machine In elligence, 19:989–1003, 1997. [10] P. N. Yianilos. Excluded middle an age poin o es s o nea es neighbo sea ch. Technical epo , NEC Resea ch Ins i u e, 1999.