000 03679nam a22005055i 4500
001 978-3-031-01851-0
003 DE-He213
005 20240730163437.0
007 cr nn 008mamaa
008 220601s2014 sz | s |||| 0|eng d
020 _a9783031018510
_9978-3-031-01851-0
024 7 _a10.1007/978-3-031-01851-0
_2doi
050 4 _aTK5105.5-5105.9
072 7 _aUKN
_2bicssc
072 7 _aCOM043000
_2bisacsh
072 7 _aUKN
_2thema
082 0 4 _a004.6
_223
100 1 _aAugsten, Nikolaus.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_978562
245 1 0 _aSimilarity Joins in Relational Database Systems
_h[electronic resource] /
_cby Nikolaus Augsten, Michael Bohlen.
250 _a1st ed. 2014.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2014.
300 _aXVII, 106 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aSynthesis Lectures on Data Management,
_x2153-5426
505 0 _aPreface -- Acknowledgments -- Introduction -- Data Types -- Edit-Based Distances -- Token-Based Distances -- Query Processing Techniques -- Filters for Token Equality Joins -- Conclusion -- Bibliography -- Authors' Biographies -- Index.
520 _aState-of-the-art database systems manage and process a variety of complex objects, including strings and trees. For such objects equality comparisons are often not meaningful and must be replaced by similarity comparisons. This book describes the concepts and techniques to incorporate similarity into database systems. We start out by discussing the properties of strings and trees, and identify the edit distance as the de facto standard for comparing complex objects. Since the edit distance is computationally expensive, token-based distances have been introduced to speed up edit distance computations. The basic idea is to decompose complex objects into sets of tokens that can be compared efficiently. Token-based distances are used to compute an approximation of the edit distance and prune expensive edit distance calculations. A key observation when computing similarity joins is that many of the object pairs, for which the similarity is computed, are very different from each other. Filters exploit this property to improve the performance of similarity joins. A filter preprocesses the input data sets and produces a set of candidate pairs. The distance function is evaluated on the candidate pairs only. We describe the essential query processing techniques for filters based on lower and upper bounds. For token equality joins we describe prefix, size, positional and partitioning filters, which can be used to avoid the computation of small intersections that are not needed since the similarity would be too low.
650 0 _aComputer networks .
_931572
650 0 _aData structures (Computer science).
_98188
650 0 _aInformation theory.
_914256
650 1 4 _aComputer Communication Networks.
_978563
650 2 4 _aData Structures and Information Theory.
_931923
700 1 _aBohlen, Michael.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_978564
710 2 _aSpringerLink (Online service)
_978565
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783031007231
776 0 8 _iPrinted edition:
_z9783031029790
830 0 _aSynthesis Lectures on Data Management,
_x2153-5426
_978566
856 4 0 _uhttps://doi.org/10.1007/978-3-031-01851-0
912 _aZDB-2-SXSC
942 _cEBK
999 _c84611
_d84611