Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication
- Publication Type
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Adapting Adtrees For Improved Performance On Large Datasets With High Arity Features, Robert D. Van Dam
Adapting Adtrees For Improved Performance On Large Datasets With High Arity Features, Robert D. Van Dam
Theses and Dissertations
The ADtree, a data structure useful for caching sufficient statistics, has been successfully adapted to grow lazily when memory is limited and to update sequentially with an incrementally updated dataset. However, even these modified forms of the ADtree still exhibit inefficiencies in terms of both space usage and query time, particularly on datasets with very high dimensionality and with high arity features. We propose five modifications to the ADtree, each of which can be used to improve size and query time under specific types of datasets and features. These modifications also provide an increased ability to precisely control how an …
Adapting Adtrees For High Arity Features, Irene Langkilde-Geary, Robert Van Dam, Dan A. Ventura
Adapting Adtrees For High Arity Features, Irene Langkilde-Geary, Robert Van Dam, Dan A. Ventura
Faculty Publications
ADtrees, a data structure useful for caching sufficient statistics, have been successfully adapted to grow lazily when memory is limited and to update sequentially with an incrementally updated dataset. For low arity symbolic features, ADtrees trade a slight increase in query time for a reduction in overall tree size. Unfortunately, for high arity features, the same technique can often result in a very large increase in query time and a nearly negligible tree size reduction. In the dynamic (lazy) version of the tree, both query time and tree size can increase for some applications. Here we present two modifications to …