The mobile industry is one that is developing rapidly. Even before current generations of mobile communications networks can be depreciated by the bean counters or even fully deployed, there will be some equipment vendors pushing next generation standards. New terms and phrases enter the industry lexicon regularly to reflect the changes.

Thus, it is hardly surprising that not many people today remember the fact that mobile phones were once commonly called cell phones.

The real reason is simple.

Mobile phones got to be mobile only in the sense that the signals being sent to and received by them were sent from fixed radio masts which defined areas of service around them or cells. Each cell is a service area defined by two things: first, a maximum service radius reached by the corresponding signal and second, a maximum number of users to be served within that radius. When users move around with the mobile phones, these cells would pass control of the signals between each other to ensure that the right signals get to the right phone; hence the term cell phone.

The problem of optimally assigning users to servers (for example, radio masts) is a classic one - and has been called many names. However, a term that has stuck is spatial optimisation, which is also a field that is researched by Kyriakos Mouratidis, professor of information systems with Singapore Management University.

Real life applications

Suppose that each signal repeater mounted on a radio mast can serve users within a 3-kilometre range from its location. Next, let's assume that each radio mast can accommodate up to a maximum of 300 users before the signal channelling becomes too congested. In this context, the telecommunications company has two objectives. First, the maximum number of users should be served. Second, the distance between users and their assigned mast should be minimised, in order to achieve the best possible connectivity. The challenge here is two-fold; that is, dealing with a large scale and with user mobility.

To get a sense of how large a scale such networks could conceivably be, consider the case of China Mobile, the world's largest mobile operator, with more than 508 million subscribers as of late 2009 - and growing. Let's say, of that half a billion users, just 2% of them are using the mobile phone while travelling in a car, therefore moving within and between cells.

Clearly, it is not a trivial matter trying to dynamically assign them to the correct cell so that the overall assignment remains optimal (in terms of total number of served users, and the average distance between users and repeaters). That movement alone would generate shifts in more than 10 million records that the database would have to update and cope with. This is a well-known problem and various attempts have been made to address it.

A different approach

The existing textbook solution - coming typically from the field of operations research - is to model it as a search problem, plotted onto a graph. However, this method is only good for hundreds or thousands of users; computationally not feasible for millions.

Mouratidis' approach to deal with such a scale is to exploit certain geometric observations along with what is termed 'spatial indexing'. Specifically, the coordinate space is conceptually divided into partitions (for example, square regions) which serve as location indexes. Each partition is then linked to the set of users that fall inside of it. This abstraction allows the graph search to run on the set of partitions, enabling it to disqualify entire groups of users (instead of individual users) as candidates to be served from specific repeaters. Also, by narrowing down the possible options, searches are completed in a shorter time.

While this pruning of the search space significantly accelerates computation for a given snapshot of the user locations, it cannot, by itself, address the second challenge, which is, dealing with frequent user movements. To deal with location updates without invoking a new search from scratch, Mouratidis puts forth an incremental evaluation principle, whereby previously computed assignments are not discarded, but simply amended to produce the new optimal assignment. This technique reuses the computational efforts paid previously, thus saving processing time and enhancing system responsiveness.

Another challenge addressed on this frontier has to do with spatial indexing itself. Data organisation for static positions has been studied for decades, giving rise to sophisticated indexing solutions that allow fast location-based retrieval. Focused on the applications at that time, the assumption underlying these indexes was that there were no or few location updates. Such organisations are not suitable for the highly dynamic scenario considered by Mouratidis, since updating the index may be too slow to cope with the frequent user movements.

To solve this problem a different approach was taken. Building and maintaining a delicate index over transient data was deemed meaningless, because by the time that diligent index adjustment is complete, the data will have already changed, requiring index maintenance anew. Instead, a very basic index is used, which may not be optimised or fine-tuned for the underlying data, but is very fast to update and efficient enough for location-based retrieval. In particular, a regular grid is used to partition the coordinate space into equi-sized square regions, each storing the user locations that fall in it.

Mouratidis' work to solve this challenging problem is not merely a description of a new algorithm. Rather, he provides data on the performance of such a method in real life situations, having implemented and tested with real datasets (via actual moving vehicle locations). Mouratidis notes: The combination of spatial pruning and incremental evaluation not only makes processing possible for a scale of millions, but it also allows the computing and updating of the optimal assignment in real-time.

Regarding his application-centred research methodology, he comments: Many researchers in the fields of theoretical computer science and computational geometry are looking into similar problems. However they are targeted at solutions of a theoretical nature, where performance is defined analytically/asymptotically in terms of worst case complexities.

On the contrary, my focus is systems-oriented in the sense that I am looking for methods that work well in practice, although they may come with no theoretical bounds about their worst case running time. There is no better way to prove 'practicality' other than demonstrating the feasibility of a solution with experiments on large scale real data; my research papers always complement algorithm/index descriptions with an extensive empirical evaluation on actual datasets, he adds.

Ongoing work

In the work sketched above, Mouratidis extended a well-studied problem to a scale where it has not been tackled before, and also dealt with, for the first time, challenge of dynamic datasets. What motivated us to work on this topic is the vast number and the mobility of users who carry location-aware devices, such as phones, PDAs, or even cameras. The increasing availability of such devices enables a generation of advanced location-based services, which, in turn, poses new research challenges.

Going forward, Mouratidis intends to develop this research area into how very large spatial databases can be managed and scaled to address real world problems, especially in the context of spatial optimisation, focusing on the large scale, spatial versions of standard operations research problems. In a parallel line of work, he plans to extend spatial processing methods and geometric reasoning to address optimisation problems of a non-spatial nature, and in particular, in the context of matching multiple user preferences with a set of available objects of interest, such as internship positions, housing options, and so on.