Oikonomou Konstantinos - Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers

Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

1234567...68

Software Tools and Distributed Architectures for Cloud-Based Data Management

Springer International Publishing AG 2017

Timos Sellis and Konstantinos Oikonomou (eds.) Algorithmic Aspects of Cloud Computing Lecture Notes in Computer Science 10230 10.1007/978-3-319-57045-7_1

NSM-Tree: Efficient Indexing on Top of NoSQL Databases

Ioannis Kokotinis 1

(1)

Computer Engineering and Informatics Department, University of Patras, 26504 Patras, Greece

(2)

Department of Informatics, Ionian University, 49100 Corfu, Greece

(3)

Department of Cultural Heritage, Management and New Technologies, University of Patras, 26504 Patras, Greece

(4)

Centre of Excellence for International Courts, University of Copenhagen, 1455 Copenhagen, Denmark

Ioannis Kokotinis

Email:

Marios Kendea

Email:

Nikolaos Nodarakis (Corresponding author)

Email:

Angeliki Rapti

Email:

Spyros Sioutas

Email:

Athanasios K. Tsakalidis

Email:

Dimitrios Tsolis

Email:

Yannis Panagis

Email:

Abstract

During the last years, there is a huge proliferation in the usage of location-based services (LBSs), mostly through a multitude of mobile devices (GPS, smartphones, mapping devices, etc.). The volume of the data derived by such services, grows exponentially and conventional databases tend to be ineffective in storing and indexing them efficiently. Ultimately, we need to turn to scalable solutions and methods using the NoSQL database model. Quite a few indexing methods exist in literature that work on top of NoSQL database. In this spirit, we deploy a new distributed indexing structure based on M-tree and perform a thorough experimental analysis to display its benefits.

Keywords

Big data Distributed index Range queries M-tree MapReduce NoSQL

Introduction

With the recent advances in GPS-enabled devices, many applications extend their functionality in order to provide geolocation features to the user. Inevitably, geographic data (or spatiotemporal data) are all around us and are produced in an enormous rate with the extensive usage of these LBSs. Such data can be proved very useful when building geographic information systems (GIS) or applications (e.g. an application that retrieves the nearest restaurants based on some user-provided parameters). Until now geographic data are stored and indexed in conventional SQL databases, which also offer many tools and methods to support location queries. However, as the data volume continues expanding traditional databases and centralized indexing schemes lack in efficiency when processing queries. Inevitably, the flourish of NoSQL databases has led to a widespread development of many new indexing structures to efficiently process queries on large-scale data.

A database indexing scheme refers to a data structure that stores on a table a small amount of information, and makes easy to retrieve any piece of database information is requested in the form of a query. Usually, this table contains the ids of others table records with appropriate references. A database driver may utilize the indexing structure for fast information access. The indexing scheme minimizes the query time as we do not need to make a full table scan to find the searched term. In order to create a database index we need to read the whole data collection from the disk and start building the structure on the main memory. If the structure is too big to fit in memory we transfer it to the disk and continue the construction as before. When this iterative process finishes, we merge the different parts of the index stored on the disk into a final bigger structure. The process to build an index over a distributed system resembles the previous one. Each node of the system creates a fraction of the structure and a unification process follows to form the final index. A suitable model to perform such a process is MapReduce [].

In this paper, we focus on implementing the popular M-Tree index [ we conclude the paper and discuss future directions.

Preliminaries

2.1 Previous Work

The research around the database indexing domain is quite extensive. Early studies focus on creating robust and efficient structures for answering range queries. One popular structure is the segment tree [].

The methods proposed above can handle data of small size in one or more dimensions, thus their use is limited in centralized environments only. During the recent years, the researchers have focused on developing approaches that are applicable in distributed environments, like our method, and can manipulate big data in an efficient manner. The MapReduce framework seems to be suitable for processing such queries. For instance, the authors in [] authors describe the new structure HB+-Tree, which is an extension of the original B+-Tree adapted to a distributed environment. In the context of this paper, we propose the NSM-Tree which is the MapReduce version of M-Tree built on top of HBase. We compare the new structured with its centralized predecessor to get an insight of the benefits of NSM-Tree.

2.2 M-Tree Overview

The M-Tree is a dynamic tree structure (generalization of B-tree) and is mainly used for indexing geospatial data. The function that calculates the distance between two points in space adheres to the theorems of symmetry and triangular inequality. The search algorithm of M-Tree is implemented as a binary search algorithm in each dimension, and is suitable for range queries in the form ( x , y ), where and .

The data stored in M-Tree is a set of the form , where key is the latitude and longitude of a point and value contains information of this location. The dataset is organized in metric spaces , where D is the center of a circle with radius d . Each node can hold up to M records and can be distinguished in two types: the leafs node that contain the sorted data, and the inner nodes that contain indexes to the actual data according to their value. For each sorted object in a leaf node there exist a record , where

Next page

1234567...68

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

Similar books «Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers»

Look at similar books to Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.

Hein Venter

Information and Cyber Security: 19th International Conference, ISSA 2020, Pretoria, South Africa, August 25–26, 2020, Revised Selected Papers

Debahuti Mishra

Intelligent and Cloud Computing: Proceedings of ICICC 2019, Volume 1

De-Shuang Huang

Intelligent Computing Theories and Application: 17th International Conference, ICIC 2021, Shenzhen, China, August 12–15, 2021, Proceedings, Part II

Yuqing Sun

Computer Supported Cooperative Work and Social Computing: 15th CCF Conference, ChineseCSCW 2020, Shenzhen, China, November 7–9, 2020, Revised Selected ... in Computer and Information Science, 1330)

Qiaohong Zu

Human Centered Computing: 6th International Conference, HCC 2020, Virtual Event, December 14–15, 2020, Revised Selected Papers

Christian Hochberger (editor)

Architecture of Computing Systems: 34th International Conference, ARCS 2021, Virtual Event, June 7–8, 2021, Proceedings

Ladjel Bellatreche

Advances in Databases and Information Systems: 25th European Conference, ADBIS 2021, Tartu, Estonia, August 24–26, 2021, Proceedings

Sabu M. Thampi (editor)

Advances in Computing and Network Communications: Proceedings of CoCoNet 2020, Volume 1: 735 (Lecture Notes in Electrical Engineering, 735)

Éric Renault (editor)

Machine Learning for Networking: Third International Conference, MLN 2020, Paris, France, November 24–26, 2020, Revised Selected Papers

Loia Vincenzo

Fuzzy Logic and Soft Computing Applications: 11th International Workshop, WILF 2016, Naples, Italy, December 19-21, 2016, Revised Selected Papers

Choi Dooho

Information Security Applications 17th International Workshop, WISA 2016, Jeju Island, Korea, August 25-27, 2016, Revised Selected Papers

Wiese

Advanced data management : for SQL, NoSQL, Cloud and distributed databases

Discussion, reviews of the book Algorithmic Aspects of Cloud Computing: Second International Workshop, ALGOCLOUD 2016, Aarhus, Denmark, August 22, 2016, Revised Selected Papers and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.