We stress the need of a domain-tailored requirements engineering method for the development of GIS-applications. To this end, we discuss three GIS-application scenarios we have frequently encountered in real life projects. Our investigation reveals that conventional RE-methods like Coad/Yourdon's Object-Oriented Analysis (OOA) are not capable of modelling GIS-specific requirements appropriately. To overcome the deficiencies of conventional OOA we introduce GEOOOA which extends OOA by domain-tailored primitives and allows for a more adequate treatment of GIS-specific requirements. We provide GEOOOA-models of three application scenarios which serve as first validation steps for the usefulness of the approach. Finally, we propose some methodological advices for a proper application of GEOOOA and sketch the GEOOOA-tool environment.

In this paper, we characterize the eciency of spatial access structures in terms of the expected number of data bucket accesses needed to perform a range query. We derive performance formulas for various kinds of range queries like intersection, containment, and enclosure queries with dierent geometric shapes. The formulas exhibit that range query performance in general depends on three parameters: the area sum of the data regions, the perimeter sum, and the number of regions. Only the weights of these parameters vary from shape to shape and query type to query type. To a wide extent, our results prove the conjecture that window queries are representative for range queries in general.

During the last decade various spatial data structures have been designed and compared against each other with respect to their performance. Still missing is a lower bound result, e.g. an optimal spatial data clustering, which would allow for the absolute comparison of the performance of the well-known data structures with the optimum. In this paper, we address the static situation where the data is known in beforehand. An optimal data clustering for this setting will also provide a lower bound for the dynamic situation where the input data is not known in advance and the data structure is built up by iterated insertions. Using as performance measure the expected number of data bucket accesses needed to perform a window query, the static clustering problem turns into a classical optimization problem. For the special case of bucket capacity cb = 2 the optimization problem is solvable in polynomial time, whereas for cb 3 it is NP-hard. In experiments using simulated annealing heuristics...

In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them. For each model, we characterize the efficiency of spatial data structures in terms of the expected number of data bucket accesses needed to perform a window query. Our analytical approach exhibits the performance phenomena independent of data structure and implementation details and whether the objects are points or non-point objects.

To guide user interface construction, concepts are needed that provide a conceptual basis for modeling, abstract notation, and implementation of tools and concrete interfaces. The authors discuss how general software engineering principles apply in this context. Following these principles, they have developed an object-oriented user interface framework, called DIWA, which consists of a design model enhanced by a declarative language for the specification of dynamic dialog behavior. The main components of the DIWA framework are addressed, and an extended discussion of the underlying design rationales is presented. The design rationale behind the DIWA system is discussed in depth. A description of the current implementation status and some ideas for future work are included.>

article Spatial priority search: an access technique for scaleless maps Share on Authors: Bruno Becker Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 Freiburg Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 FreiburgView Profile , Hans-Werner Six Praktische Informatik III, FernUniversität Hagen, Postfach 940 D-5800 Hagen Praktische Informatik III, FernUniversität Hagen, Postfach 940 D-5800 HagenView Profile , Peter Widmayer Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 Freiburg Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 FreiburgView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991 pp 128–137https://doi.org/10.1145/119995.115805Online:01 April 1991Publication History 25citation340DownloadsMetricsTotal Citations25Total Downloads340Last 12 Months7Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In many nonstandard database applications, spatial access to geometric objects is very important. A new access structure, the R-file, is presented for geometric objects in a dynamic environment. An extensive performance evaluation reveals that the R-file, which is based on handling axis-parallel rectangles in secondary storage, has higher storage space utilization and a more compact directory, and turns out to be more efficient in exact match and window queries than comparable schemes, e.g. R-trees or grid file variants, for example, for maintaining geometric objects.>

Presents a dynamic, globally order-preserving hashing technique, based on linear hashing, where the spatial proximity of points is preserved beyond data buckets. The method adaptively generates a bucket numbering, which is a flexible variant of the well-known z-ordering. In addition to the standard dictionary operations, the authors' dynamic z-hashing scheme supports the efficient implementation of proximity queries.>

A principle is presented for transforming suitable index structures for points into index structures for k-dimensional intervals. In many applications, these intervals serve as simple geometric keys for nonzero-size objects. The transformation fully preserves the advantages of the selected index structure for points, such as efficient update and retrieval operations, especially range queries, as well as high storage space utilization. The authors have implemented an index structure for rectangles based on the grid file. A performance evaluation with geographic data shows highly encouraging results.>

Storage 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.

To sort an external file on a random access device, the merge sort is the generally accepted method. We present a new algorithm based on Quicksort which allows sorting of external files in situ. Analytical results and a comparison of test runs indicate that when the new algorithm is applied to a file with suitable key structure, it is competitive to the merge sort in terms of run-time behaviour.

We investigate three cost measures for the recently introduced brother search trees. In particular we characterize node visit optimal, comparison-cost optimal and space-cost optimal 1-2 brother trees and present linear-time algorithms to construct optimal 1-2 brother trees for each cost measure. Furthermore we also consider, briefly, these cost measures for brother leaf search trees.

We present a solution to the problem of reporting and counting all pairs of intersecting or overlapping d-ranges in a given set of n d-ranges. A d-range is a rectilinearly oriented rectangular d-dimensional box or brick. The three-dimensional case is presented in some detail and an 0(n log22n + k) time and 0(n log22n) space algorithm is developed for the reporting problem, where k is the number of reported intersecting pairs. This gives an 0(n log22n) time and 0(n log2n) space algorithm for the counting problem. Apart from its usefulness wherever a "bounding boxes" technique is used, the development of the algorithm is of interest in its own right because of the data structures that are introduced and because of the technique used to reduce the time needed for preprocessing. Finally, the algorithm is generalized to give an 0(2d−1n log2d−n+ k) time and an 0(2d−1n log2d−n) space algorithm for the d-range intersection reporting problem for d ≥ 2, which again reduces to an 0(2d−1n log2d−1n) time and 0(2d−1n log2d−2n) space algorithm for the counting problem. Finally, we sketch how the reporting problem can be carried out with the same space requirements as the counting problem. The bounds presented are the best known to date.