{"_id":"cWRwDHaNRhDEdRyfa","bibbaseid":"wang-yang-muntz-informationorganizationanddatabasesfoundationsofdataorganization-2000","downloads":0,"creationDate":"2016-02-18T13:03:32.351Z","title":"Information Organization and Databases: Foundations of Data Organization","author_short":["Wang, W.","Yang, J.","Muntz, R."],"year":2000,"bibtype":"inbook","biburl":"https://dl.dropboxusercontent.com/u/26998770/main.bib","bibdata":{"bibtype":"inbook","type":"inbook","abstract":"In this chapter we present the PK-tree which is an index structure for high dimensional point data. The proposed indexing structure can be viewed as combining aspects of the PR-quad or K-D tree but where unnecessary nodes are eliminated. The unnecessary nodes are typically the result of skew in the point distribution and we show that by eliminating these nodes the performance of the resulting index is robust to skewed data distributions. The index structure is formally defined, efficiently updateable and bounds on the number of nodes and the mean height of the tree can be proved. Bounds on the expected height of the tree can be given under certain mild constraints on the spatial distribution of points. Empirical evidence both on real data sets and generated data sets shows that the PK-tree outperforms the recently proposed spatial indexes based on the R-tree and X-tree by a wide margin. It is also significant that the relative performance advantage of the PK-tree grows with the dimensionality of the data set. ","address":"Norwell, MA","author":[{"propositions":[],"lastnames":["Wang"],"firstnames":["W."],"suffixes":[]},{"propositions":[],"lastnames":["Yang"],"firstnames":["J."],"suffixes":[]},{"propositions":[],"lastnames":["Muntz"],"firstnames":["R."],"suffixes":[]}],"chapter":"PK-tree: A Spatial Index Structure for High Dimensional Point Data","date-added":"2008-07-22 09:45:22 -0400","date-modified":"2008-07-22 09:48:06 -0400","keywords":"spatial; index; database; nearest neighbor","pages":"281--293","publisher":"Kluwer Academic Publishers","series":"Kluwer International Series In Engineering And Computer Science Series","title":"Information Organization and Databases: Foundations of Data Organization","year":"2000","bdsk-file-1":"YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RElpOUy5vYmplY3RzViRjbGFzc1dOUy5rZXlzog8QgASABoAHohMUgAKAA1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgMGRpXTlMuZGF0YU8RAZQAAAAAAZQAAgAAA212IAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAMU5bQNIKwAAABCNbRZwa3RyZWUtd2FuZy1ib29rLTAwLnBzAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEI+/xKtdigAAAAAAAAAAAAIAAwAACSAAAAAAAAAAAAAAAAAAAAAIYXJ0aWNsZXMAEAAIAADFObNTAAAAEQAIAADEq5XKAAAAAQAQABCNbQAKTIAACkxpAAB8EwACADltdiA6VXNlcnM6cmd1aGE6RG9jdW1lbnRzOmFydGljbGVzOnBrdHJlZS13YW5nLWJvb2stMDAucHMAAA4ALgAWAHAAawB0AHIAZQBlAC0AdwBhAG4AZwAtAGIAbwBvAGsALQAwADAALgBwAHMADwAIAAMAbQB2ACAAEgA1VXNlcnMvcmd1aGEvRG9jdW1lbnRzL2FydGljbGVzL3BrdHJlZS13YW5nLWJvb2stMDAucHMAABMAAS8AABUAAgAM//8AAIAF0hwdHh9YJGNsYXNzZXNaJGNsYXNzbmFtZaMfICFdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3RfEC8uLi8uLi9Eb2N1bWVudHMvYXJ0aWNsZXMvcGt0cmVlLXdhbmctYm9vay0wMC5wc9IcHSQloiUhXE5TRGljdGlvbmFyeRIAAYagXxAPTlNLZXllZEFyY2hpdmVyAAgAEQAWAB8AKAAyADUAOgA8AEUASwBSAF0AZABsAG8AcQBzAHUAeAB6AHwAhgCTAJgAoAI4AjoCPwJIAlMCVwJlAmwCdQKnAqwCrwK8AsEAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAAC0w==","bibtex":"@inbook{Wang:2000aa,\n\tAbstract = {In this chapter we present the PK-tree which is an index structure for high dimensional point data. The proposed indexing structure can be viewed as combining aspects of the PR-quad or K-D tree but where unnecessary nodes are eliminated. The unnecessary nodes are typically the result of skew in the point distribution and we show that by eliminating these nodes the performance of the resulting index is robust to skewed data distributions. The index structure is formally defined, efficiently updateable and bounds on the number of nodes and the mean height of the tree can be proved. Bounds on the expected height of the tree can be given under certain mild constraints on the spatial distribution of points. Empirical evidence both on real data sets and generated data sets shows that the PK-tree outperforms the recently proposed spatial indexes based on the R-tree and X-tree by a wide margin. It is also significant that the relative performance advantage of the PK-tree grows with the dimensionality of the data set. },\n\tAddress = {Norwell, MA},\n\tAuthor = {Wang, W. and Yang, J. and Muntz, R.},\n\tChapter = {{PK}-tree: A Spatial Index Structure for High Dimensional Point Data},\n\tDate-Added = {2008-07-22 09:45:22 -0400},\n\tDate-Modified = {2008-07-22 09:48:06 -0400},\n\tKeywords = {spatial; index; database; nearest neighbor},\n\tPages = {281--293},\n\tPublisher = {Kluwer Academic Publishers},\n\tSeries = {Kluwer International Series In Engineering And Computer Science Series},\n\tTitle = {Information Organization and Databases: Foundations of Data Organization},\n\tYear = {2000},\n\tBdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RElpOUy5vYmplY3RzViRjbGFzc1dOUy5rZXlzog8QgASABoAHohMUgAKAA1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgMGRpXTlMuZGF0YU8RAZQAAAAAAZQAAgAAA212IAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAMU5bQNIKwAAABCNbRZwa3RyZWUtd2FuZy1ib29rLTAwLnBzAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEI+/xKtdigAAAAAAAAAAAAIAAwAACSAAAAAAAAAAAAAAAAAAAAAIYXJ0aWNsZXMAEAAIAADFObNTAAAAEQAIAADEq5XKAAAAAQAQABCNbQAKTIAACkxpAAB8EwACADltdiA6VXNlcnM6cmd1aGE6RG9jdW1lbnRzOmFydGljbGVzOnBrdHJlZS13YW5nLWJvb2stMDAucHMAAA4ALgAWAHAAawB0AHIAZQBlAC0AdwBhAG4AZwAtAGIAbwBvAGsALQAwADAALgBwAHMADwAIAAMAbQB2ACAAEgA1VXNlcnMvcmd1aGEvRG9jdW1lbnRzL2FydGljbGVzL3BrdHJlZS13YW5nLWJvb2stMDAucHMAABMAAS8AABUAAgAM//8AAIAF0hwdHh9YJGNsYXNzZXNaJGNsYXNzbmFtZaMfICFdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3RfEC8uLi8uLi9Eb2N1bWVudHMvYXJ0aWNsZXMvcGt0cmVlLXdhbmctYm9vay0wMC5wc9IcHSQloiUhXE5TRGljdGlvbmFyeRIAAYagXxAPTlNLZXllZEFyY2hpdmVyAAgAEQAWAB8AKAAyADUAOgA8AEUASwBSAF0AZABsAG8AcQBzAHUAeAB6AHwAhgCTAJgAoAI4AjoCPwJIAlMCVwJlAmwCdQKnAqwCrwK8AsEAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAAC0w==}}\n\n","author_short":["Wang, W.","Yang, J.","Muntz, R."],"key":"Wang:2000aa","id":"Wang:2000aa","bibbaseid":"wang-yang-muntz-informationorganizationanddatabasesfoundationsofdataorganization-2000","role":"author","urls":{},"keyword":["spatial; index; database; nearest neighbor"],"downloads":0},"search_terms":["information","organization","databases","foundations","data","organization","wang","yang","muntz"],"keywords":["spatial; index; database; nearest neighbor"],"authorIDs":[],"dataSources":["c5japf9eAQRaeMS4h"]}