?:Arya, S.
M. Mount, D.
Netanyahu, N.S.
Silverman, R.
Wu, A.1994?An optimal algorithm for approximate nearest neighbor searching5735821In Proc. 5th ACMSIAM Sympos. Discrete Algorithmshttp://citeseer.nj.nec.com/arya94optimal.html*F?Blelloch, G.
Narlikar, G.1997+A Practical Comparison of Nbody AlgorithmsXIn Parallel Algorithms, Series in Discrete Mathematics and Theoretical Computer Science.This work compares three algorithms for the three dimensional Nbody problem, the BarnesHut algorithm, Greengard's Fast Multipole Method(FMM), and the Parallel Multipole Tree Algorithm (PMTA) to determine which of the algorithms performs best in practice. Although FMM has a better asymptotic running time (O(N) instead of O(N log N) for uniform distributions), the algorithm is more complicated and it is not immediately clear above what values of N it performs better in practice. We studied the dependence of accuracy on the variable parameters theta, p and alpha, and then compared the floating point operation counts of the three algorithms at similar levels of accuracy, for both charged and uncharged random distributions. At a high level of accuracy (RMSerror ~= 10^5), the FMM did the least number of operations for N > 10^4, assuming both charged and uncharged distributions of points. At a lower level of accuracy, (RMSerror ~= 10^3) for uncharged distributions, the FMM did not outperform BarnesHut even for N > 10^8. For charged distributions of particles, both the FMM and PMTA were comparable at low accuracy. The algorithms were implemented in the parallel language NESL.Vhttp://www2.cs.cmu.edu/afs/cs.cmu.edu/project/scandal/public/papers/dimacsnbody.htmlcompared three treebased algorithms, the BarnesHut algorithm [2], Greengard's Fast Multipole algorithm [9], and the Multipole Tree algorithm [6], in terms of both the computational cost and the accuracy of the methods.
http://www2.cs.cmu.edu/~scandal/alg/nbody.html?"Bustos, B.
Navarro, G.
Ch'avez, E.2001CPivot selection techniques for proximity searching in metric spaces3340^In Proc. of the XXI Conference of the Chilean Computer Science Society (SCCC'01) IEEE CS Presshttp://citeseer.nj.nec.com/bustos01pivot.html*?Callahan, P.B.1993ROptimal parallel allnearestneighbors using the wellseparated pair decomposition3323410In Proc. 34th Annu. ACM Sympos. Found. Comp. Sci1http://citeseer.nj.nec.com/callahan93optimal.html*?$Chávez, E.
Figueroa, K.
Navarro, G.1983RA Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces.226232;In Proc. 24th IEEE Symp. on Foundations of Computer Science'http://citeseer.ist.psu.edu/462760.html? Callahan, P. B.
Kosaraju, S. Rao1995?Algorithms for Dynamic Closest Pair and nBody Potential Fields263272<In Proc. 6th ACMSIAM Sympos. Discrete Algorithms (SODA '95)%http://citeseer.nj.nec.com/99546.html*D?Clarkson, K. L.19835Fast algorithms for the all nearest neighbors problem2262323In Proc. 24th Annu. IEEE Sympos. Found. Comput. ScigSIMD architecture, knearest neighbor, parallel processing, data analysis, reconfigurable mesh computerGiven a set S of m points stored on a reconfigurable mesh computer of size n×n, one point per processing element (PE). In this paper we present a parallel method for solving the kNearest Neighbor problem (kNN). This method permits each point of S to know its kNN (0 0, we produce a data structure, such that given any query point, a point of S will be reported whose distance from the query point is at most a factor of (1 + E) from that of the true nearest neighbor. Our algorithm runs in O(log3 n) expected time and requires O(n log n) space. The data structure can be built in O(n’) expected time. The constant factors depend on d and 6. Because of the practical importance of nearest neighbor searching in higher dimensions, we have implemented a practical variant of this algorithm,and show empirically that for many point distributions this variant of the algorithm finds the nearest neighbor in moderately large dimension significantly faster than existing practical approaches.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=313768&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735?
0898713137?0Chon, Hae Don
Agrawal, Divyakant
Abbadi, Amr El2003?Range and kNN Query Processing for Moving Objects in Grid Model401412 Mobile Networks and Applications84With the growing popularity of mobile computing devices and wireless communications, managing dynamically changing information about moving objects is becoming feasible. In this paper, we implement a system that manages such information and propose two query algorithms: a range query algorithm and a k nearest neighbor algorithm. The range query algorithm is combined with an efficient filtering technique which determines if a polyline corresponding to the trajectory of a moving object intersects with a given range. We study the performance of the system, which shows that despite the filtering step, for moderately large ranges, the range query algorithm we propose outperforms the algorithm without filtering.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=942352&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735 1383469X?Yufei Tao
Dimitris Papadias2003'Spatial Queries in Dynamic Environments101139+ACM Transactions on Database Systems (TODS)282hConventional spatial queries are usually meaningless in dynamic environments since their results may be invalidated as soon as the query or data objects move. In this paper we formulate two novel query types, time parameterized and continuous queries, applicable in such environments. A timeparameterized query retrieves the actual result at the time when the query is issued, the expiry time of the result given the current motion of the query and database objects, and the change that causes the expiration. A continuous query retrieves tuples of the form , where each result is accompanied by a future interval, during which it is valid. We study timeparameterized and continuous versions of the most common spatial queries (i.e., window queries, nearest neighbors, spatial joins), proposing efficient processing algorithms and accurate cost models.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=777944&coll=Portal&dl=GUIDE&CFID=20411976&CFTOKEN=50968782 03625915?"Ciaccia, P.
Patella, M.
Zezula, P.1997IMtree: An Efficient Access Method for Similarity Search in Metric Spaces426435,Very Large Data Bases (VDLP) Conference 1997A new access method, called Mtree, is proposed to organize and search large data sets from a generic “metric space”, i.e. where object proximity is only defined by a distance function satisfying the positivity, symmetry, and triangle inequality postulates. We detail algorithms for insertion of objects and split management, which keep the Mtree always balanced  several heuristic split alternatives are considered and experimentally evaluated. Algorithms for similarity (range and knearest neighbors) queries are also described. Results from extensive experimentation with a prototype system are reported, considering as the performance criteria the number of page I/O’s and the number of distance computations. The results demonstrate that the Mtree indeed extends the domain of applicability beyond the traditional vector spaces, performs reasonably well in highdimensional data spaces, and scales well in case of growing files./http://citeseer.ist.psu.edu/ciaccia97mtree.html
1558604707s?Yianilos, P.1993SData Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces311321In Proc. ACMSIAM SODA'930Metric Space, Nearest Neighbor, KDtree, VPtreenWe consider the computational problem of finding nearest neighbors in general metric spaces. Of particular interest are spaces that may not be conveniently embedded or approximated in Euclidian space, or where the dimensionality of a Euclidian representation is very high.
Also relevant are highdimensional Euclidian settings in which the distribution of data is in some sense of lower dimension and embedded in the space. The vptree (vantage point tree) is introduced in several forms, together with associated algorithms, as an improved method for these difficult search problems. Tree construction executes in O(n log(n)) time, and search is under certain circumstances and in the limit, O(long(n)) expected time.
The theoretical basis for this approach is developed and the results of several experiments are reported. In Euclideian cases, kdtree performance is compared./http://citeseer.ist.psu.edu/yianilos93data.html?Bentley, J. L.1975CMultidimensional Binary Search Trees Used For Associative Searching509517.Communications of the ACM, 18(9): September 75associative retrieval, attribute, binary search trees, binary tree insertion, information retrieval system, intersection queries, key, nearest neighbor queries, partial match queriesThis paper develops the multidimensional binary search tree (or kd tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The kd tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O(log n); deletion of the root, O(n(k1)/k); deletion of a random node, O(log n); and optimization (guarantees logarithmic performance of searches), O(n log n). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O(n(kt)/k)] and for nearest neighbor queries [empirically observed average running time of O(log n).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that kd trees could be quite useful in many applications, and examples of potential uses are given.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=361007&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735CITINGS 147 00010782FF?
Berchtold, S.19968The Xtree: An Index Structure for HighDimensional Data'Proceedings of the 22nd VLDB, August 96In this paper, we propose a new method for indexing large amounts of point and spatial data in highdimensional space. An analysis shows that index structures such as the R*tree are not adequate for indexing highdimensional data sets. The major problem of Rtreebased index structures is the overlap of the bounding boxes in the directory, which increases with growing dimension. To avoid this problem, we introduce a new organization of the directory which uses a split algorithm minimizing overlap and additionally utilizes the concept of supernodes. The basic idea of overlapminimizing split and supernodes is to keep the directory as hierarchical as possible, and at the same time to avoid splits in the directory that would result in high overlap. Our experiments show that for highdimensional data, the Xtree outperforms the wellknown R*tree and the TVtree by up to two orders of magnitude.1http://citeseer.ist.psu.edu/berchtold96xtree.html?Guttman, A.19848Rtrees: A Dynamic Index Structure for Spatial Searching4757OIn proceedings of the ACM SIGMOD International Conference on Management of DataIn order to handle spatial data efficiently, as required in computer aided design and geodata applications, a database system needs an index mechanism that will help it retrieve data items quickly according to their spatial locations However, traditional indexing methods are not well suited to data objects of nonzero size located m multidimensional spaces In this paper we describe a dynamic index structure called an Rtree which meets this need, and give algorithms for searching and updating it. We present the results of a series of tests which indicate that the structure performs well, and conclude that it is useful for current database systems in spatial applications.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=602266&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735
0897911288?,Nievergelt, J.
Hinterberger, H.
Sevcik, K.C.1984>The Grid File: An Adaptable, Symmetric Multikey File Structure3871+ACM Transactions on Database Systems (TODS)91mTraditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for singlekey access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a grid partition of the search space and of a grid directory, which are the keys to a dynamic file structure called the grid file. This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=318586&coll=Portal&dl=GUIDE&CFID=20239473&CFTOKEN=33442915 03625915t?,Fu, A. W.
Chan, P. M.
Cheung, Y.
Moon, Y. S.2000PDynamic VPTree Indexing for NNearest Neighbor Search Given PairWise Distances154173EThe VLDB Journal  The International Journal on Very Large Data Bases92whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=765232&coll=Portal&dl=GUIDE&CFID=20255546&CFTOKEN=38486040 10668888$? Robinson, J.T.1981MThe KDBtree: a search structure for large multidimensional dynamic indexes1018TIn Proceedings of the 1981 ACM SIGMOD international conference on Management of data?http://portal.acm.org/citation.cfm?id=582321&dl=ACM&coll=portal
0897910400iB?!k,Yu, B.
Orlandic, R.
Bailey, T.
Somavaram, J.2003KKDBKDTree: A Compact KDBTree Structure for Indexing Multidimensional DatafIn Proceedings of the International Conference on Information Technology: Computers and CommunicationsThe problem of storing and retrieving highdimensional data continues to be an important issue. Inthis paper, we propose an efficient highdimensional pointaccess method called the KDBKDtree.The KDBKDtreeeliminates redundant information in KDBtrees bychanging the representation of the index entries in theinterior pages. Experimental evidence shows that theKDBKDTree outperforms other recent variants of KDBtrees, such as KDBFDtrees and KDBHDtrees.%http://www.cs.uwyo.edu/~yu/ITCC03.pdf
0769519164?"FBeckmann, Norbert
Kriegel, HansPeter
Schneider, Ralf
Seeger, Bernhard1990LThe R*tree: An Efficient and Robust Access Method for Points and Rectangles322331OIn Proceedings of the ACM SIGMOD international conference on Management of data1The Rtree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R*tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R*tree clearly outperforms the existing Rtree variants. Guttman's linear and quadratic Rtree and Greene's variant of the Rtree. This superiority of the R*tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R*tree is very attractive because of the following two reasons 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other Rtrees.vhttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=98741&coll=Portal&dl=GUIDE&CFID=20255546&CFTOKEN=38486040 01635808?#Theodoridis, Y
Sellis, T19960A Model for the Prediction of Rtree Performance161171dIn Proceedings of the fifteenth ACM SIGACTSIGMODSIGART symposium on Principles of database systems@In this paper we present an analytical model that predicts the performance of Rtrees (and its variants) when a range query needs to be answered. The cost model uses knowledge of the dataset only, i.e., the proposed formula that estimates the number of disk accesses is a hmction of data properties, namely, the amount of data and their density in the work space. In other words, the proposed model is applicable even before the construction of the Rtree index, a fact that makes it a useful tool for dynamic spatial databases. Several experiments on synthetic and real datasets show that the proposed analytical model is very accurate, the relative error being usually around 10% 15%, for uniform and nonuniform distributions. We believe that this error is involved with the gap between efficient Rtree variants, like the R*tree,
and an optimum, not implemented yet, method. Our work extends previous research concerning Rtree analysis and constitutes a useful tool for spatial query optimizers that need to evaluate the cost of a complex spatial query and its execution procedure.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=237705&coll=Portal&dl=GUIDE&CFID=20255546&CFTOKEN=38486040
0897917812?$0Lin, King Ip
Jagadish, H. V.
Faloutsos, Christos19949The TVtree: an index structure for highdimensional data517542EThe VLDB Journal  The International Journal on Very Large Data Bases34We propose a file structure to index highdimensionality data, which are typically points in some feature space. The idea is to use only a few of the features, using additional features only when the additional discriminatory power is absolutely necessary. We present in detail the design of our tree structure and the associated algorithms that handle such "varying length" feature vectors. Finally, we report simulation results, comparing the proposed structure with the R*tree, which is one of the most successful methods for lowdimensionality spaces. The results illustrate the superiority of our method, which saves up to 80% in disk accesses.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=615210&coll=Portal&dl=GUIDE&CFID=20255470&CFTOKEN=52246893 10668888?%White, D.A.
Jain, R.1996$Similarity Indexing with the SStree516523GProceedings of the Twelfth International Conference on Data EngineeringEfficient indexing of high dimensional feature vectors is important to allow visual information systems and a number other applications to scale up to large databases. In this paper, we define this problem as "similarity indexing" and describe the fundamental types of "similarity queries" that we believe should be supported. We also propose a new dynamic structure for similarity indexing called the similarity search tree or SStree. In nearly every test we performed on high dimensional data, we found that this structure performed better than the R*tree. Our tests also show that the SStree is much better suited for approximate queries than the R*tree.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=655573&coll=Portal&dl=GUIDE&CFID=20255470&CFTOKEN=52246893CITINGS 14
0818672404/?'1Saltenis, S.
Jensen, C.
Leutenegger, S.
Lopez, M.20026Indexing of Moving Objects for LocationBased Services463DProceedings of the 18th International Conference on Data EngineeringXAccess method, Moving objects, Rtree, Locationbased service, Multidimensional indexingVisionaries predict that the Internet will soon extend to billions of wireless devices, or objects, a substantial fraction of which will offer their changing positions to locationbased services. This paper assumes an Internetservice scenario where objects that have not reported their position within a specified duration of time are expected to no longer be interested in, or of interest to, the service. Due to the possibility of many "expiring" objects, a highly dynamic database results.The paper presents an Rtree based technique for the indexing of the current positions of such objects. Different types of bounding regions are studied, and new algorithms are provided for maintaining the tree structure. Performance experiments indicate that, when compared to the approach where the objects are not assumed to expire, the new indexing technique can improve search performance by a factor of two or more without sacrificing update performance.>http://portal.acm.org/citation.cfm?id=878984&dl=ACM&coll=GUIDE 10636382?(#Agarwal, P.K.
Arge, L.
Erickson, J.2003Indexing Moving Points207243'Journal of Computer and System Sciences661We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that any query of the following form can be answered quickly: Given a rectangle R and a real value t, report all K points of S that lie inside R at time t. We first present an indexing structure that, for any given constant e > 0, uses O(N/B) disk blocks and answers a query in O(N/B1/2+e + K/B)I/Os, where B is the block size. It can also report all the points of S that lie inside R during a given time interval. A point can be inserted or deleted, or the trajectory of a point can be changed, in O(log2BN) I/Os. Next, we present a general approach that improves the query time if the queries arrive in chronological order, by allowing the index to evolve over time. We obtain a tradeoff between the query time and the number of times the index needs to be updated as the points move. We also describe an indexing scheme in which the number of I/Os required to answer a query depends monotonically on the difference between the query time stamp t and the current time. Finally, we develop an efficient indexing scheme to answer approximate nearestneighbor queries among moving points.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=846166&coll=Portal&dl=GUIDE&CFID=20411976&CFTOKEN=50968782 00220000P?)%Basch, J.
Guibas, L.J.
Hershberger J.1997Data Structures for Mobile Data747756JProceedings of the eighth annual ACMSIAM symposium on Discrete algorithmswhttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=314435&dl=GUIDE&coll=Portal&CFID=20411976&CFTOKEN=50968782haven't read
0898713900:?* Basch, J.
Guibas, L.J.
Zhang, l.1997#Proximity problems on moving points344351HProceedings of the thirteenth annual symposium on Computational geometryA kinetic data structure for the maintenance of a multidimensional range search tree is introduced. This structure is used as a building block to obtain kinetic data structures for two classical geometric proximity problems in arbitrary dlmensions: the first structure maintains the closest pair of a set of continuously moving points, and is provably efficient. The second structure maintains a spanning tree of the moving points whose cost remains within some prescribed factor of the minimum spanning tree.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=262998&dl=GUIDE&coll=Portal&CFID=20411976&CFTOKEN=50968782
0897918789AF?+,Tao, Yufei
Papadias, Dimitris
Shen, Qiongmao2002"Continuous Nearest Neighbor Search*In Proceedings of the 28th VLDB ConferencesA continuous nearest neighbor query retrieves the nearest neighbor (NN) of every point on a line segment (e.g., “find all my nearest gas stations during my route from point s to point e”). The result contains a set of tuples, such that point is the NN of all points in the corresponding interval. Existing methods for continuous nearest neighbor search are based on the repetitive application of simple NN algorithms, which incurs significant overhead. In this paper we propose techniques that solve the problem by performing a single query for the whole input segment. As a result the cost, depending on the query and dataset characteristics, may drop by orders of magnitude. In addition, we propose analytical models for the expected size of the output, as well as, the cost of
query processing, and extend out techniques to several variations of the problem.(http://www.vldb.org/conf/2002/S09P02.pdf
looks okay?,0Zhang, J.
Zhu, M.
Papadias, D.
Tao, Y.
Lee, D.L.2003Locationbased Spatial Queries443454TProceedings of the 2003 ACM SIGMOD international conference on on Management of data
might be okay!In this paper we propose an approach that enables mobile clients to determine the validity of previous queries based on their current locations. In order to make this possible, the server returns in addition to the query result, a validity region around the client's location within which the result remains the same. We focus on two of the most common spatial query types, namely nearest neighbor and window queries, define the validity region in each case and propose the corresponding query processing algorithms. In addition, we provide analytical models for estimating the expected size of the validity region. Our techniques can significantly reduce the number of queries issued to the server, while introducing minimal computational and network overhead compared to traditional spatial queries.vhttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=872812&coll=Portal&dl=GUIDE&CFID=20303748&CFTOKEN=2062914?
158113634Xj?:Freidman, Jerome H.
Bentley, Jon Louis
Finkel, Raphael Ari1977BAn Algorithm for Finding Best Matches in Logarithmic Expected Time2092260ACM Transactions on Mathematical Software (TOMS)33best matches, nearest neighbors, file searching, computational geometry, associative searching, search trees, multidmiensional searching,An algorithm and data structure are presented for searching a file containing N records, each described by k real valued keys, for the m closest matches or nearest neighbors to a given query record. The computation required to organize the file is proportional to kN log N. The expected number of records examined in each search is independent of the file size. The expected computation to perform each search is proportional to log N. Empirical evidence suggests that, except for very small files, this algorithm is considerably faster than other methods.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=355745&coll=Portal&dl=GUIDE&CFID=20333779&CFTOKEN=92886735NMedian kd  A refined kdtree, using median cuts and bucketing.
haven't read. 00983500]?.BFaloutsos, Christos
Seeger, Bernhard
Traina, Agma
Traina, Caetano2000)Spatial Join Selectivity Using Power Laws177188pACM SIGMOD Record , Proceedings of the 2000 ACM SIGMOD international conference on Management of data (May 2000)292We discovered a surprising law governing the spatial join selectivity across two sets of points. An example of such a spatial join is “find the libraries that are within 10 miles of schools”. Our law dictates that the number of such qualifying pairs follows a power law, whose exponent we call “paircount exponent” (PC). We show that this law also holds for selfspatialjoins (“find schools within 5 miles of other schools”) in addition to the general case that the two pointsets are distinct. Our law holds for many real datasets, including diverse environments (geographic datasets, feature vectors from biology data, galaxy data from astronomy).
In addition, we introduce the concept of the BoxOccupancyProductSum (BOPS) plot, and we show that it can compute the paircount exponent in a timely manner, reducing the run time by orders of magnitude, from quadratic to linear. Due to the paircount exponent and our analysis (Law 1), we can achieve accurate selectivity estimates in constant time (O(1)) without the need for sampling or other expensive operations. The relative error in selectivity is about 30% with our fast BOPS method, and even better (about 10%), if we use the slower, quadratic method.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=335412&coll=Portal&dl=GUIDE&CFID=20509324&CFTOKEN=19821135 01635808 ?/!Hjaltason, Gísli R.
Samet, Hanan1999&Distance Browsing in Spatial Databases265318+ACM Transactions on Database Systems (TODS)242DWe compare two different techniques for browsing through a collection of spatial objects stored in an Rtree spatial data structure on the basis of their distances from an arbitrary spatial query object. The conventional approach is one that makes use of a knearest neighbor algorithm where k is known prior to the invocation of the algorithm. Thus if m < k neighbors are needed, the knearest neighbor algorithm has to be reinvoked for m neighbors, thereby possibly performing some redundant computations. The second approach is incremental in the sense that having obtained the k nearest neighbors, the k + 1st neighbor can be obtained without having to calculate the k + 1 nearest neighbors from scratch. The incremental approach is useful when processing complex queries where one of the conditions involves spatial proximity (e.g., the nearest city to Chicago with population greater than a million), in which case a query engine can make use of a pipelined strategy. We present a general incremental nearest neighbor algorithm that is applicable to a large class of hierarchical spatial data structures. This algorithm is adapted to the Rtree and its performance is compared to an existing knearest neighbor algorithm for Rtrees [Rousseopoulos et al. 1995]. Experiments show that the incremental nearest neighbor algorithm significantly outperforms the knearest neighbor algorithm for distance browsing queries in a spatial database that uses the Rtree as a spatial index. Moreover, the incremental nearest neighbor algorithm usually outperforms the knearest neighber algorithm when applied to the knearest neighbor problem for the Rtree, although the improvement is not nearly as large as for distance browsing queries. In fact, we prove informally that at any step in its execution the incremental nearest neighbor algorithm is optimal with respect to the spatial data structure that is employed. Furthermore, based on some simplifying assumptions, we prove that in two dimensions the number of distance computations and leaf nodes accesses made by the algorithm for finding k neighbors is O(k + k).whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=320255&coll=Portal&dl=GUIDE&CFID=20385494&CFTOKEN=184394430BF improvement on Nearest Neighbor Queries paper 03625915?0Daniel A. Keim1999BEfficient geometrybased similarity search of 3D spatial databases419430QProceedings of the 1999 ACM SIGMOD international conference on Management of data
Searching a database of 3Dvolume objects for objects which are similar to a given 3D search object is an important problem which arises in number of database applications  for example, in Medicine and CAD. In this paper, we present a new geometrybased solution to the problem of searching for similar 3Dvolume objects. The problem is motivated from a real application in the medical domain where volume similarity is used as a basis for surgery decisions. Our solution for an efficient similarity search on large databases of 3D volume objects is based on a new geometric index structure. The basic idea of our new approach is to use the concept of hierarchical approximations of the 3D objects to speed up the search process. We formally show the correctness of our new approach and introduce two instantiations of our general idea, which are based on cuboid and octree approximations. We finally provide a performance evaluation of our new index structure revealing significant performance improvements over existing approaches.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=304219&coll=Portal&dl=GUIDE&CFID=20526069&CFTOKEN=901841176?
seems okay___ MIV=approximating region to grid boxes 01635808?15Authors SangWook Kim
Charu C. Aggarwal
Philip S. Yu2001=Effective Nearest Neighbor Indexing with the Euclidean Metric916YProceedings of the tenth international conference on Information and knowledge management\The nearest neighbor search is an important operation widelyused in multimedia databases. In higher dimensions, most of previous methods for nearest neighbor search become inefficient and require to compute nearest neighbor distances to a large fraction of points in the space. In this paper, we present a new approach for processing nearest neighbor search with the Euclidean metric, which searches over only a small subset of the original space. This approach effectively approximates clusters by encapsulating them into geometrically regular shapes and also computes better upper and lower bounds of the distances from the query point to the clusters. For showing the effectiveness of the proposed approach, we perform extensive experiments. The results reveal that the proposed approach significantly outperforms the Xtree as well as the sequential scan.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=502588&coll=Portal&dl=GUIDE&CFID=20526069&CFTOKEN=90184117'?
says better than Xtree high dims....
15811343636F?2AMihael Ankerst
Gabi Kastenmüller
HansPeter Kriegel
Thomas Seidl19997Nearest Neighbor Classification in 3D Protein DatabasesgSource Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology3443d3D Protein Databases, Nearest Neighbor Classification, Geometric Similarity Search, Machine Learning<In molecular databases, structural classification is a basic task that can be successfully approached by nearest neighbormethods. The underlying similarity models consider spatialproperties such as shape and extension as well as thematic attributes. We introduce 3D shape histograms as an intuitive and powerful approach to model similarity for solid objects such as molecules. Errors of measurement, sampling, and numerical rounding may result in small displacements of atomic coordinates. These effects may be handled by using quadratic form distance functions. An efficient processing of similarity queries based on quadratic forms is supported by a filterrefinement architecture. Experiments on our 3D protein database demonstrate the high classification accuracy of more than 90% and the good performance of the technique.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=660824&coll=Portal&dl=GUIDE&CFID=20526069&CFTOKEN=90184117?
1577350839?3Böhm, Christian2000AA Cost Model for Query Processing in HighDimensional Data Spaces129178?Source ACM Transactions on Database Systems (TODS) (June 2000)252gDuring the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research topic in multimedia databases is similarity search in large data sets. Most current approaches that address similarity search use the feature approach, which transforms important properties of the stored objects into points of a highdimensional space (feature vectors). Thus, similarity search is transformed into a neighborhood search in feature space. Multidimensional index structures are usually applied when managing feature vectors. Query processing can be improved substantially with optimization techniques such as blocksize optimization, data space quantization, and dimension reduction. To determine optimal parameters, an accurate estimate of indexbased query processing performance is crucial. In this paper we develop a cost model for index structures for point databases such as the R*tree and the Xtree. It provides accurate estimates of the number of data page accesses for range queries and nearestneighbor queries under a Euclidean metric and a maximum metric and a maximum metric. The problems specific to highdimensional data spaces, called boundary effects, are considered. The concept of the fractal dimension is used to take the effects of correlated data into account.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=357776&coll=Portal&dl=GUIDE&CFID=20385494&CFTOKEN=18439443SURVEY!!!
Looks good 03625915'?4Warren, M. S.
Salmon, J. K.1992HAstrophysical Nbody Simulations using Hierarchical Tree Data Structures570576=Proceedings of the 1992 ACM/IEEE conference on SupercomputingnbodyWe report on recent large astrophysical Nbody simulations executed on the Intel Touchstone Delta system. We review the astrophysical motivation, and the numerical techniques, and discuss steps taken to parallelize these simulations. The methods scale as O(N log N), for large values of N, and also scale linearly with the number of processors. The performance, sustained for a duration of 67 hours was between 5.1 and 5.4 Gj70p/sec on a 51,2 processor system.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=148090&coll=Portal&dl=GUIDE&CFID=20668623&CFTOKEN=51137664
0818626305?59Papadopoulos, Apostolos
Rigaux, Philippe
Scholl, Michel1999>A Performance Evaluation of Spatial Join Processing Strategies286307OProceedings of the 6th International Symposium on Advances in Spatial DatabasesoWe provide an evaluation of query execution plans (QEP) in the case of queries with one or two spatial joins. The QEPs assume R*tree indexed relations and use a common set of spatial joins algorithms, among which one is a novel extension of a strategy based on an onthefly index creation prior to the join with another indexed relation. A common platform is used on which a set of spatial access methods and join algorithms are available. The QEPs are implemented with a general iteratorbased spatial query processor, allowing for pipelined QEP execution, thus minimizing memory space required for intermediate results.*http://www.lri.fr/~rigaux/publis/PRS99.pdfnot read
35406624725?6Gaede, Volker
Günther, Oliver1998Multidimensional Access Methods1702317Source ACM Computing Surveys (CSUR) archive (June 1998)3020data structures, multidimensional access methodsSearch operations in databases require special support at the physical level. This is true for conventional databases as well as spatial databases, where typical search operations include the point query (find all objects that contain a given search point) and the region query (find all objects that overlap a given search region). More than ten years of spatial database research have resulted in a great variety of multidimensional access methods to support such operations. We give an overview of that work. After a brief survey of spatial data management in general, we first present the class of point access methods, which are used to search sets of points in two or more dimensions. The second part of the paper is devoted to spatial access methods to handle extended objects, such as rectangles or polyhedra. We conclude with a discussion of theoretical and experimental results concerning the relative performance of various approaches.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=280279&coll=Portal&dl=GUIDE&CFID=20544313&CFTOKEN=89100490"++
BRILLIANT, but long
CITINGS 86 03600300'?7EFagin, Ronald
Nievergelt, Jurg
Pippenger, Nicholas
Strong, H. Raymond1979;Extendible Hashing  A Fast Access Method for Dynamic Files315344KSource ACM Transactions on Database Systems (TODS) archive (September 1979)43Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=320092&dl=GUIDE&coll=Portal&CFID=20544313&CFTOKEN=89100490

not read 03625915?84Faloutsos, Christos
Sellis, Timos
Roussopoulos, Nick19872Analysis of Object Oriented Spatial Access Methods426439QProceedings of the 1987 ACM SIGMOD international conference on Management of dataeThis paper provides an analysis of Rtrees and a variation (R+trees) that avoids overlapping rectangles in intermediate nodes of the tree. The main contributions of the paper are the following. We provide the first known analysis of Rtrees. Although formulas are given for objects in one dimension (line segments), they can be generalized for objects in higher dimensions as well. We show how the the transformation of objects to higher dimenslons [HINR83] can be effectively used as a tool for the analysis of R and R+ trees. Finally, we derive formulas for R+trees and compare the two methods analytically. The results we obtained show that R+trees require less than half the disk accesses required by a corresponding Rtree when searching files of real hfe sizes R+trees are clearly superior in cases where there are few long segments and a lot of small ones.vhttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=38758&dl=GUIDE&coll=Portal&CFID=20544313&CFTOKEN=89100490
not so great. 01635808q?9Tamminen, Markku
Sulonen, Reijo19828The EXCELL Method for Efficient Geometric Access to Data345351:Proceedings of the nineteenth design automation conference"The extendible cell (EXCELL) method provides a data structure for efficient geometric access. It stores geometric data into computer storage blocks corresponding to disjoint variable sized rectangular cells accessible by an address calculation type directory. We describe the method for point files and files of more complicated figures analyzing performance. We report algorithms for the nearest neighbour and pointinpolygonnetwork problems and describe applications to geographical data bases, hidden line elimination and geometric modeling.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=809228&coll=Portal&dl=GUIDE&CFID=20577822&CFTOKEN=14769457 Will use!
0897910206?:Freeston, Michael1987&The BANG file: A new kind of grid file260269QProceedings of the 1987 ACM SIGMOD international conference on Management of dataA new multidimensional file structure has been developed in the course of a project to devise ways of improving the support for interactive queries to database and knowledge bases. Christened the 'BANG' file  a Balanced And Nested Grid  the new structure is of the 'grid file' type, but is fundamentally different from previous grid file designs in that it does not share their common underlying properties. It has a treestructured directory which has the selfbalancing property of a Btree and which, in contrast to previous designs, always expands at the same rate as the data, whatever the form of the data distribution. Its partitioning strategy both accurately reflects the clustering of points in the data space, and is flexible enough to adapt gracefully to changes in the distribution.Bhttp://portal.acm.org/citation.cfm?id=38743&dl=ACM&coll=GUIDE#opub 01635808:?;$Seeger, Bernhard
Kriegel, HansPeter1990SThe Buddy Tree: An Efficient and Robust Access Method for Spatial Data Base Systems590601TSource Proceedings of the sixteenth international conference on Very large databasesIn this paper, we propose a new multidimensional access method, called the buddytree, to support point as well as spatial data in a dynamic environment. The buddytree can be seen as a compromise of the Rtree and the grid file, but it is fundamentally different from each of them. Because grid files loose performance for highly correlated data, the buddytree is designed to organize such data very efficiently, partitioning only such parts of the data space which contain data and not partitioning empty data space. The directory consists of a very flexible partitioning and reorganization scheme based on a generalization of the buddysystem. As for Btrees, the buddytree fulfills the property that insertions and deletions are restricted to exactly one path of the directory. Additional important properties which are not fulfilled in this combination by any other multidimensional treebased access method are: (i) the directory grows linear in the number of records, (ii) no overflow pages are allowed, (iii) the data space is partitioned into minimum bounding rectangles of the actual data and (iv) the performance is basicly independent of the sequence of insertions. In this paper, we introduce the principles of the buddytree, the organization of its directory and the most important algorithms. Using our standardized testbed, we present a performance comparison of the buddytree with other access methods demonstrating the superiority and robustness of the buddytree.fhttp://portal.acm.org/citation.cfm?id=94615&dl=GUIDE&coll=GUIDE
http://www.vldb.org/conf/1990/P590.PDF
055860149X?<Klaus Hinrichs1985?Implementation of the grid file: design concepts and experience569592254=
http://portal.acm.org/citation.cfm?id=5039&dl=ACM&coll=GUIDE
CANT FIND 00063835?=3Hutflesz, Andreas
Six, HansWerner
Widmayer, Peter19880Twin Grid Files: Space Optimizing Access Schemes183190QProceedings of the 1988 ACM SIGMOD international conference on Management of dataStorage access schemes for points, supporting spatial searching, usually suffer from an undesirably low storage space utilization. We show how a given set of points can be distributed among two grid files in such a way that storage space utilization is optimal. The optimal twin grid file can be built practically as fast as a standard grid file, i.e., the storage space optimality is obtained at almost no extra cost. We compare the performances of the standard grid file, the optimal static twin grid file, and an efficient dynamic twin grid file, where insertions and deletions trigger the redistribution of points among the two grid files. Twin grid files utilize storage space at roughly 90%, as compared with the 69% of the standard grid file. Typical range queries  the most important spatial search operations  can be answered in twin grid files at least as fast as in the standard grid file.=http://portal.acm.org/citation.cfm?id=50222&dl=ACM&coll=GUIDE
0897912683?>Mireille Regnier1985 Analysis of Grid File Algorithms335358BIT archive252uhttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=3823&coll=Portal&dl=GUIDE&CFID=20579400&CFTOKEN=32601696$
NOT DOWNLOADED
CITINGS 6
FRENCH? 00063835??=Kalashnikov, Dmitri V.
Prabhakar, Sunil
Hambrusch, Susanne E.2004@Main Memory Evaluation of Monitoring Queries Over Moving Objects1171357Distributed and Parallel Databases archive (March 2004)152In this paper we evaluate several inmemory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects or fraction of objects that move at any moment in time. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hitrate. Experimental evaluation establishes that indexing queries using the grid index yields orders of magnitude better performance than other index structures such as R*trees.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=966448&coll=Portal&dl=GUIDE&CFID=20689990&CFTOKEN=77331203IAlmost 100% identical to "Efficient Evaluation of Moving Points ..." 2002 09268782@?@Samet, Hanan19902The Design and Analysis of Spatial Data Structures493Boston, MA, USA*AddisonWesley Longman Publishing Co., Inc=http://portal.acm.org/citation.cfm?id=77589&dl=ACM&coll=GUIDE)WOULD BE GOOD TO GET A COPY
CITINGS 199
0201502550$AddisonWesley Longman Publishing Co?A"Kamel, Ibrahim
Faloutsos, Christos19941Hilbert Rtree: An Improved Rtree using Fractals500509MProceedings of the Twentieth International Conference on Very Large DatabasesWe propose a new Rtree structure that outperforms all the older ones. The heart of the idea is to facilitate the deferred splitting approach in Rtrees. This is done by proposing an ordering on the Rtree nodes. This ordering has to be 'good', in the sense that it should group 'similar' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Following [19] we have chosen the socalled '2Dc' method, which sorts rectangles according to the Hilbert value of the center of the rectangles. Given the ordering, every node has a well defined set of sibling nodes; thus, we can use deferred splitting. By adjusting the split policy, the Hilbert Rtree can achieve as high utilization as desired. To the contrary, the R \Lambda tree has no control over the space utilization, typically achieving up to 70%. We designed the manipulation algorithms in detail, and we did a full implementation of the Hilbert Rtree. Our experiments show that the '2to3' split policy provides a compromise between the insertion complexity and the search cost, giving up to 28% savings over the R \Lambda \Gamma tree [3] on real data.(citeseer.ist.psu.edu/kamel94hilbert.html?B/Christian Böhm
Stefan Berchtold
Daniel A. Keim2001mSearching in Highdimensional Spaces  Index Structures for Improving the Performance of Multimedia Databases3223735ACM Computing Surveys (CSUR) archive (September 2001)333?During the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research issue in the field of multimedia databases is the contentbased retrieval of similar multimedia objects such as images, text, and videos. However, in contrast to searching data in a relational database, a contentbased retrieval requires the search of similar objects as a basic functionality of the database system. Most of the approaches addressing similarity search use a socalled feature transformation that transforms important properties of the multimedia objects into highdimensional points (feature vectors). Thus, the similarity search is transformed into a search of points in the feature space that are close to a given query point in the highdimensional feature space. Query processing in highdimensional spaces has therefore been a very active research area over the last few years. A number of new index structures and algorithms have been proposed. It has been shown that the new index structures considerably improve the performance in querying large multimedia databases. Based on recent tutorials [Berchtold and Keim 1998], in this survey we provide an overview of the current state of the art in querying multimedia databases, describing the index structures and algorithms for an efficient query processing in highdimensional spaces. We identify the problems of processing queries in highdimensional space, and we provide an overview of the proposed approaches to overcome these problems.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=502809&coll=Portal&dl=GUIDE&CFID=20807916&CFTOKEN=47254095?? 03600300e?CLawder, J. K.
King, P. J. H.2001MQuerying multidimensional data indexed using the Hilbert spacefilling curve1924ACM SIGMOD Record (March 2001)301Mapping to onedimensional values and then using a onedimensional indexing method has been proposed as a way of indexing multidimensional data. Most previous related work uses the ZOrder Curve but more recently the Hilbert Curve has been considered since it has superior clustering properties. Any approach, however, can only be of practical value if there are effective methods for executing range and partial match queries. This paper describes such a method for the Hilbert Curve.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=373678&coll=Portal&dl=GUIDE&CFID=20699715&CFTOKEN=95585171?
Might be good to use  cool diagram  divide using quadrants. 01635808?DDBongki Moon
H. v. Jagadish
Christos Faloutsos
Joel H. Saltz2001HAnalysis of the Clustering Properties of the Hilbert SpaceFilling Curve1241413IEEE Transactions on Knowledge and Data Engineering131localitypreserving linear mapping, range queries, multiattribute access methods, data clustering, Hilbert curve, spacefilling curves, fractals.Several schemes for the linear mapping of a multidimensional space have been proposed for various applications, such as access methods for spatiotemporal databases and image compression. In these applications, one of the most desired properties from such linear mappings is clustering, which means the locality between objects in the multidimensional space being preserved in the linear space. It is widely believed that the Hilbert spacefilling curve achieves the best clustering [1], [14]. In this paper, we analyze the clustering property of the Hilbert spacefilling curve by deriving closedform formulas for the number of clusters in a given query region of an arbitrary shape (e.g., polygons and polyhedra). Both the asymptotic solution for the general case and the exact solution for a special case generalize previous work [14]. They agree with the empirical results that the number of clusters depends on the hypersurface area of the query region and not on its hypervolume. We also show that the Hilbert curve achieves better clustering than the z curve. From a practical point of view, the formulas given in this paper provide a simple measure that can be used to predict the required disk access behaviors and, hence, the total access time.http://citeseer.ist.psu.edu/cache/papers/cs/101/ftp:zSzzSzftp.cs.umd.eduzSzpubzSzhpslzSzpaperszSzhilberttr.pdf/moon96analysis.pdf/
CITINGS 4 10414347?EAbel, D.J.
Mark. D. M.19908A Comparative Analysis of Some TwoDimensional Orderings2131Int. J. Geograph. Inf. Syst41COULD NOT FIND ANYWHERE!!!!!4?FErcolessi, F1997A Molecular Dynamics Primer2004
01072004ICTP,http://www.fisica.uniud.it/~ercolessi/md/md/G+
http://diamond.kist.re[F?GJ. A. Izaguirre
T. Matthey20043Parallel multigrid summation for the Nbody problemHsubmitted to Journal of Parallel and Distributed Computing (20 Feb 2004)]parallel Nbody solvers, multigrid summation, fast electrostatic
solvers, particle meshEwaldAn (n) parallel multigrid summation method for the Nbody problem is presented. The method works with vacuum or periodic boundary conditions. It is based on a hierarchical decomposition of computational kernels on multiple grids. For low accuracy calculations, appropriate for molecular dynamics, a sequential implementation is faster than both Fast Multipole and Particle Mesh Ewald (PME). Its parallel implementation is more scalable than PME and comparable to the fast multipole. The method can be combined with multiple time stepping integrators to produce a powerful simulation protocol for simulation of biological molecules and other materials. The parallel implementation is based on MPI, and is tested in a variety of clusters and shared memory computers. It is available as opensource in http://protomol.sourceforge.net. An auxiliary tool allows the automatic selection of optimal parameters for given molecular systems and accuracies required, and is available in http://mdsimaid.cse.nd.edu..http://www.ii.uib.no/~matthey/text/paper12.pdf(+
Great references ect,NOT PUBLISHED!!
+#?H!R. D. Skeel
I. Tezcan
D. J. Hardy20026Multiple Grid Methods for Classical Molecular Dynamics673684J. Comp. Chem. 236_Nbody solver; multigrid method; fast multipole method; fast electrostatics; molecular dynamicsPresented in the context of classical molecular mechanics and dynamics are multilevel summation methods for the fast calculation of energies/forces for pairwise interactions, which are based on the hierarchical interpolation of interaction potentials on multiple grids. The concepts and details underlying multigrid interpolation are described. For integration of molecular dynamics the use of different time steps for different interactions allows longer time steps for many of the interactions, and this can be combined with multiple grids in space. Comparison is made to the fast multipole method, and evidence is presented suggesting that for molecular simulations multigrid methods may be superior to the fast multipole method and other tree methods.3http://www.ks.uiuc.edu/~dhardy/preprints/SkTH02.pdfP?IL. Greengard
V. Rokhlin1987)A Fast Algorithm for Particle Simulations3253480Journal of Computational Physics (December 1987)732San Diego, CA, USA!Academic Press Professional, Inc.>http://portal.acm.org/citation.cfm?id=36901&dl=ACM&coll=portal)
COULD NOT FIND COPY  THINK IS BOOK :( 00219991.?J!T. Bishop
R. D. Skeel
K. Schulten1997^Difficulties with Multiple Timestepping and the Fast Multipole Algorithm in Molecular Dynamics 17851791J. Comp. Chem.1814Vmultiple time steps; rRESPA; Verlet method; molecular dynamics;
fast multipole methodNumerical experiments are performed on a 36,000atom proteinDNAwater simulation to ascertain the effectiveness of two devices for reducing the time spent computing longrange electrostatics interactions. It is shown for VerletIrrRESPA multiple time stepping, which is based on approximating longrange forces as widely separated impulses, that a long time step of 5 fs results in a dramatic energy drift and that this is reduced by using an even larger long time step. It is also shown that the use of as many as six terms in a fast multipole algorithm approximation to longrange electrostatics still fails to prevent significant energy drift even though four digits of accuracy
is obtained.Bhttp://www.ks.uiuc.edu/Publications/Papers/PDF/BISH97A/BISH97A.pdf
not sure about it3?KE. L. Pollock
Jim Glosli1996PComments on PPPM, FMM, and the Ewald Method for Large Periodic Coulombic Systems93110"Computer Physics Communications 95Prompted by the need to simulate large molecular or gravitational systems and the availability of multiprocessor computers, alternatives to the standard Ewald calculation of Coulombic interactions have been developed. The two most popular alternatives, the fast multipole method (FMM) and the particleparticle particlemesh (P3M) method are compared here to the Ewald method for a single processor machine. Parallel processor implementations of the P3M and Ewald methods are compared. The P3Mmethod is found to be both faster than the FMM and easier to implement efficiently as it relies on commonly available software (FFT subroutines). Both the Ewald and P3M method are easily implemented on parallel architectures with the P3M method the clear choice for large systems.7http://arxiv.org/PS_cache/condmat/pdf/9511/9511134.pdf?+
NOT READ
Apparently says PPM = better & easier to implement!?L'Ananth Y. Grama
Vipin Kumar
Ahmed Sameh1994NScalable Parallel Formulations of the BarnesHut Method for nBody Simulations439448=Proceedings of the 1994 ACM/IEEE conference on SupercomputingIn this paper, we present two new parallel formulations of the BarnesHut method. These parallel formulations are especially suited for simulations with irregular particle densities. We first present a parallel formulation that uses a static partitioning of the domain and assignment of subdomains to processors. We demonstrate that this scheme delivers acceptable load balance, and coupled with two collective communication operations, it yields good performance. We present a second parallel formulation which combines static decomposition of the domain with an assignment of subdomains to processors based on Morton ordering. This alleviates the load imbalance inherent in the first scheme. The second parallel formulation is inspired by two currently best known parallel algorithms for the BarnesHut method. We present an experimental evaluation of these schemes on a 256 processor nCUBE2 parallel computer for an astrophysical simulation.whttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=602846&coll=Portal&dl=GUIDE&CFID=21484757&CFTOKEN=13317159
Doesn't look that great 10639535?NM.P. Allen
D.J. Tildesley1987Computer Simulation of LiquidsNew YorkOxford University Press
GREAT BOOK!!!?OJ. E. Barnes
P. Hut19863A Hierarchical O(NlogN) Force Calculation Algorithm446449Nature3244A novel code for the approximate computation of longrange forces between N mutually interacting bodies is presented. The code is based on a hierarchical tree of cubic cells and features mutual cellcell interactions which are calculated via a Cartesian Taylor expansion in a symmetric way, such that total momentum is conserved. The code benefits from an improved and simple multipole acceptance criterion that reduces the force error and the computational effort. For N ~> 104, the computational costs are found empirically to rise sublinear with N. For applications in stellar dynamics, this is the first competitive code with complexity O(N), it is faster than the standard tree code by a factor ten or more.7http://arxiv.org/PS_cache/astroph/pdf/0202/0202512.pdf<Origional fast multipole method.Voted in "best 10 algotihms"?PVinit Jain
Ben Shneiderman1994NData Structures for Dynamic Queries: An Analytical and Experimental Evaluation1119Proceedings of the workshop on Advanced visual interfacesDynamic Queries is a querying technique for doing range search on multikey data sets. It is a direct manipulation mechanism where the query is formulated using graphical widgets and the results are displayed graphically preferably within 100 milliseconds.This paper evaluates four data structures, the multilist, the grid file, kd tree and the quad tree used to organize data in high speed storage for dynamic queries. The effect of factors like size, distribution and dimensionality of data on the storage overhead and the speed of search is explored. Analytical models for estimating the storage and the search overheads are presented, and verified to be correct by empirical data. Results indicate that multilists are suitable for small (few thousand points) data sets irrespective of the data distribution. For large data sets the grid files are excellent for uniformly distributed data, and trees are good for skewed data distributions. There was no significant difference in performance between the tree structures.vhttp://80portal.acm.org.elibrary.jcu.edu.au/citation.cfm?id=192313&coll=Portal&dl=GUIDE&CFID=21652029&CFTOKEN=74585814Says: grid best for uniform, trees better for skewed
0897917332?QR. W. Hockney
J. W. Eastwood1988#Computer Simulation using Particles564Bristol, PA, USA Publisher Taylor & Francis, Inc.>http://portal.acm.org/citation.cfm?id=62815&dl=ACM&coll=portalVery good  copy at library
0852743920_?RDaan Frenkel
Berend Smit1996CUnderstanding Molecular Simulation: From Algorithms to Applications443Academic PressLondon
0122673514DUnderstanding Molecular Simulation : From Algorithms to ApplicationsO?SBjarne Stroustrup2000.The C++ Programming Language (Special Edition)IndianapolisPearson EducationSpecial Edition
0201700735.The C++ Programming Language (Special Edition)The C++ Programming Languagec/?TScott Meyers2003More Effective C++318035 New Ways to Improve Your PrograO?UScott Meyers2003
Effective C++256550 Specific Ways to Improve Your Programs and DesignsIndianapolisAddisonWesleySecond Edition
0201924889 ;ms and DesignsIndianapolisAddisonWesley
020163371X?VCharlotte Froese Fischer1977!The HartreeFock method for atoms3209The HartreeFock method for atoms : a numerical approach New YorkJohn Wiley & Sons Inc
047125990X!/CSD981012.pdfnot published!F?WLoup Verlet1968dComputer "Experiments" on Classical Fluids. I. Thermodynamical Properties of LennardJones MoleculesPhysical Review159?XAndrew Noske2004lMolecular Dynamics Simulation and Other SelfSpatial Join  an Engine Layer and Performance Testing Platform2004
26/11/2004%http://www.krimzon.net/~noske/thesis/GIncludes a "testing platform", with all code used in compiling results for this thesis, and also contains a minimal implementation of a "grid engine" layer (including only the most successful techniques in this thesis), which has how to use it to execute efficient molecular dynamic (or other) pairwise interaction simulation.?Y Microsoft2004)C++ Language Reference  Data Type Ranges 8/11/2004Qhttp://msdn.microsoft.com/library/enus/vclang/html/_langref_data_type_ranges.aspu.kr/SMS/papers/Ercolessi%20%20MD%20Primer.pdfDhttp://diamond.kist.re.kr/SMS/papers/Ercolessi%20%20MD%20Primer.pdfۿZDmitry Konovalov2004TOMSK group20049/20045/2004'http://www.it.jcu.edu.au/~dmitry/tomsk/$Towards Molecular Structure KineticsTOMSK group!http://www.it.jcu.edu.au/~dmitry/5/2004