# MR*-Tree: Novel Indexing and Retrieving Mechanism for Spatial Objects in Mobile PowerPoint Pages

Authors: Jianming Xiang; ZhangBing Zhou; Lei Shu; Cong Liu; Qun Wang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Different from the traditional office software, due to the limited storage and computational capability of mobile devices, how to support the page editing in a fast and energy-efficient manner is fundamental. To address this challenge, we propose an MR*-tree based indexing mechanism for supporting the fast and energy-efficient retrieval of spatial objects in mobile PowerPoint pages. Based on this, techniques are developed to support the operations when editing mobile PowerPoint pages. Prototype has been implemented for facilitating the operations of spatial objects when editing mobile PowerPoint pages. Experimental evaluations on computers, pads, and smart phones show the effectiveness and efficiency of this technique.


---

## Body

## 1. Introduction

Nowadays, the mobile devices are widely used in the life of people, largely due to the development of mobile communication technology and the increasing coverage positioning technology [1]. Besides, the more endurability of battery can make the mobile devices operate for a longer time and support more computational-intensive applications, which are usually supported by computers traditionally [2]. These indicate that mobile devices are taking a role that is more and more important in many aspects of people’s life [3–6]. Along with the blossoming of the mobile Internet, mobile applications are used widely and the mobile office has been a popular software for users who travel often, which let the users work using any mobile device and at any time and place, whenever and wherever there is an Internet access. This has promoted the demand for mobile office to a large extent [7]. A good mobile office application should let users deal with anything with the software at any time in any place, getting rid of the limitation of the screen size and the computational capacity of devices [8–10].It is worth mentioning that, compared with the traditional office software, the mobile office does not require to support the complete functionalities. Instead, fast and accurate response to users’ requests is essential, including accurate cursor locating, guideline generation for facilitating images, and full-text transformation from one place to another when editing pages. This is fundamental especially when users edit mobile PowerPoint pages [9]. With the relatively large number of spatial objects in a mobile PowerPoint page and relatively small storage and computational capabilities in smart phones, PDA, or other mobile devices, an energy-efficient technique of managing these spatial objects, which can facilitate the mobile PowerPoint page editing, is required for mitigating the problems described as follows.(i) Data of Big Volume for Spatial Objects with respect to the Limited Storage Capacity of Mobile Devices [11]. The rapidly increasing volume of data makes a great demand for the storage capacity of smart devices, where the location data contributes with a majority of the storage capacity and computational resources. Consequently, a more effective data structure is required for organising the location data more efficiently. Generally, the location data is represented in terms of (
a
,
b
), where a, b denote the X- and Y-coordinates of a spatial object. In this setting, a spatial index is constructed, which can consume less memory and disk space while supporting the operations of spatial objects.(ii) The Complex Query Processing of Spatial Data with respect to Relatively Low Performance of Smart Devices [12–15]. Traditional relational database is not appropriate for storing and querying spatial objects, and an efficient spatial indexing mechanism is necessary for facilitating the query processing of spatial objects with limited storage and computation capability of mobile devices.To address the challenges discussed above, a spatial objects indexing mechanism, denoted byMR
∗-tree, is proposed leveraging the traditional R∗-tree method [16], which can index spatial objects in PowerPoint pages efficiently and effectively. Thereafter, operations are developed for locating a cursor, selecting letters, and generating guidelines. Experimental evaluations on pads and smart phones show the effectiveness of this proposed technique.The rest of this paper will be organized as follows. In Section2, we introduce the model of the mobile PowerPoint and build a spatial index on spatial objects in mobile PowerPoint pages. In Section 3, we present the model of some operations for mobile PowerPoint pages and develop algorithms for supporting these operations. In Section 4, experiments are conducted for evaluating the applicability and efficiency of proposed algorithms. In Section 5, relevant techniques are discussed and reviewed, and finally we conclude this work in Section 6.


## 2. Indexing Spatial Objects

In this section, we will present how to organise spatial objects in mobile office PoewrPoint by means of the spatial index. Generally, the structure of PowerPoint is shown in Figure1 [17], and the description of these structural elements is shown in Table 1.Table 1
Structural elements of mobile PowerPoint.
Name
Description
ShapeFrame
Top container of spatial objects in the PowerPoint which contains all the text contents
TextFrame
Subcontainer ofShapeFrame and the object for setting the attributes for the paragraph in PowerPoint pages
LineFrame
Subcontainer ofTextFrame and the object of a text line in the paragraph, which prescribes how the text line displays
LineLayout
Subcontainer of theLineFrame and the container of words in the same size in a text line
TextPotion
Container of the text with the same attributes
TailPorion
Container of the placeholder in a text line
sldFrm
Superior container containing allShapeFrames in PowerPoint pages and there is one sldFrm in one PowerPoint pageFigure 1
Structure of a PowerPoint page.The spatial indexes are built onShapeFrame andTextPortion, since they are either the largest or the smallest containers of the pages in PowerPoint. The reason why we cannot build spatial indexes on every kind of container is that a page could include multipleShapeFrames and there can be multiple subcontainers in the superior containers, which leads to the unacceptable time complexity O
(
N
6
), where N is the amount of spatial object in the PowerPoint page. So, we address this problem by building spatial index on two kinds of containers, where the time complexity is O
(
N
2
). And the reason why we chooseShapeFrame andTextPortion is that we usually present the images in theShapeFrame while the texts are presented in the Texportion, which include most content of a PowerPoint page. A spatial index is constructed as detailed by Algorithm 1, whereShapeRTree is constructed as a variable ofsldFrm andTextPortionRTree is saved as a variable in the currentShapeFrame.Algorithm 1:Building spatial index on spatial objects.
Require:
s
l
d
F
r
m: superior container of a PowerPoint page
Ensure:
ShapeRTree and TextPotionRTree are constructed
(1)  while  s
l
d
F
r
m
.
C
u
r
r
e
n
t
≠
n
u
l
l  do
(2)   if  s
l
d
F
r
m
.
C
u
r
r
e
n
t
=
S
h
a
p
e
F
r
a
m
e  then
(3)    add s
l
d
F
r
m
.
C
u
r
r
e
n
t to s
l
d
F
r
m
.
S
h
a
p
e
R
T
r
e
e
(4)    while  S
h
a
p
e
F
r
a
m
e
.
C
u
r
r
e
n
t
≠
n
u
l
l  do
(5)     if  S
h
a
p
e
F
r
a
m
e
.
C
u
r
r
e
n
t
=
T
e
x
t
P
o
r
t
i
o
n  then
(6)      add S
h
a
p
e
F
r
a
m
e
.
C
u
r
r
e
n
t to S
h
a
p
e
F
r
a
m
e
.
T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
(7)     end if
(8)     S
h
a
p
e
F
r
a
m
e
.
C
u
r
r
e
n
t
← next object in S
h
a
p
e
F
r
a
m
e
(9)    end while
(10)  end if
(1
1)  s
l
d
F
r
m
.
C
u
r
r
e
n
t
← next object in s
l
d
F
r
m
(1
2) end whileGenerally, we retrieve objects insldFrm (line 1). For eachShapeFrame insldFrm, we add it as an element of the spatial indexsldFrm.ShapeRTree (lines 2-3). Then,ShapeFrame is treated as a loop object, and everyTextPortion inShapeFrame will be added to the spatial indexShapeFrame.TextPortionRTree (lines 6–9). Consequently, the spatial indexes ofShapeFrame andTextPortion are constructed. The spatial indexes are represented asrectangles, which specify the the bound of the spatial object using the elements ofmaxX,maxY,minX, andminY.


## 3. Retrieving Operations for Spatial Objects

This section will present the mechanisms of optimizing the operations of mobile applications leveraging the spatial indexes constructed in the previous section. We first show the expansion of the spatial relationship of spatial objects, which should simplify the procedure of retrieving objects. Generally, the method of retrieving arectangle depends on three types of spatial relationships, namely,contains,intersect, andnearest, wherecontains means that the object is surrounded by the samerectangle andintersect means that the spatial object overlaps with therectangle, whilenearest specifies that the bounds of the object andrectangle are close enough. We have built the expansion retrieving method on the relation ofnearest as shown in Figure 2, because the relationships betweenintersect andcontains are clear and definite. Thenearest can be classified intoVertNearest andHrzNearest, which return therectangle, the X- or Y-coordinates of which are nearest to the object. Furthermore, theVertNearest can be classified into (i)VertUpNearest which returns the nearestrectangle having a bigger Y and (ii)VertDownNearest which returns the nearestrectangle having a smaller Y. There is a similar classification ofHrzNearest, which isHrzLeftNearest andHrzRightNearest. Every subclassification can be divided into two classes, which returns therectangle nearest in a specific area (such asAreaVertUpNearest) and returns therectangle neatest in the limit range of X (such asVertAreaUpNearest). Actually, a relationship can be treated as a java function packaged in the ClassMRTree. TheMRTree is implemented based on the open source online project Java Spatial Index (JSI), which provides the implementation of rapid and efficient basic spatial relationships, such asnearest. Then, we expand these operations to provide the functions of more coarser in granularity, such asHrzAraRightNearst. The spatial index built on the PowerPoint pages is the input as a parameter of the Java functions. Based on these spatial relations, we present in the following section how the cursor, letters, and guidelines are retrieved for supporting mobile applications.Figure 2
The expansion on the relationship ofnearest.


### 3.1. Operation of Locating a Cursor

Cursor location is basically locating apoint in the page of PowerPoint. The model ofpoint retrieve object is shown in Figure 3, where there are two types of zones in a simple page of a PowerPoint, which are (i) letter zones and (ii) zones around the letters. Generally, when we touch the page by fingers, we are giving the instruction of producing a cursor by the location where we have touched.(i)
When the finger point is located upon the letters, this means that thepoint retrieve object is located in the letters zone. In this case, the spatial index will (i) retrieve therectangle which is nearest to or containedby thepoint retrieve object and (ii) produce the cursor after theTextPortion mapping to therectangle.
(ii)
Otherwise, thepoint retrieve object is located in the zone around the letters, and there will be eight conditions that determine the location of the cursor as follows.
(a)
Zone a. The cursor should be located before the firstTextPortion of the first line.
(b)
Zone b. The cursor should be located after the correspondingTextPortion of the first line.
(c)
Zone c. The cursor should be located after the lastTextPortion of the first line.
(d)
Zone d. The cursor should be located before the firstTextPortion of the line which is nearest to thepoint retrieve object.
(e)
Zone e. The cursor should be located after the lastTextPortion of the line which is nearest to thepoint retrieve object.
(f)
Zone f. The cursor should be located before the firstTextPortion of the last line.
(g)
Zone g. The cursor should be located after the correspondingTextPortion of the last line.
(h)
Zone h. The cursor should be located after the lastTextPortion of the last line.Figure 3
The model of apoint retrieve object.The procedure of locating the cursor based on the location of finger point is described by Algorithm2. Note that the spatial index ofTextPortion constructed in Section 2 improves the performance ofrectangle retrieving. Firstly,TextPortion is initialized asnull (line 1). The spatial indexTextPortionRTree is retrieved to examine whether there is aTextPortion containing the location where the finger point locates (lines 2–7). If the point is located in a certainTextPortion, the procedure terminates and the currentTextPortion is returned (line 5). Otherwise, the spatial relationship ofnearest is used for determining whetherTextPortion and the finger point are in the relation of horizontal (line 8) or vertical (line 15) situations and retrievingTextPortion which is nearest the finger point. Thereafter,TextPortion is expanded as arectangle of the row and usesareaHrzNearest to find aTextPortion where the cursor should be covered (lines 8–14 and lines 15–26). Note that this is different fromnearest for the horizontal and vertical situations. WhenVertNearest
≠
n
u
l
l, we will verify whether the finger point is under all of theTextPortion and returnHrzNearest when the finger point is at the bottom (lines 16-17). The time complexity is O
(
n
), where n is the number of spatial objects.Algorithm 2:Locating the cursor.
Require:
P: the point where the finger locates
Ensure:
T
e
x
t
P
o
r
t
i
o
n: TextPortion where the cursor locates
(1)   T
e
x
t
P
o
r
t
i
o
n
←
n
u
l
l
(2)   while  S
h
a
p
e
F
r
a
m
e
.
T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
C
u
r
r
e
n
t
≠
n
u
l
l  do
(3)    if  T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
C
u
r
r
e
n
t  c
o
n
t
a
i
n
s  P  then
(4)     T
e
x
t
P
o
r
t
i
o
n
←
T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
C
u
r
r
e
n
t
(5)     return  T
e
x
t
P
o
r
t
i
o
n
(6)    end if
(7)   end while
(8)   if  P
.
h
r
z
A
r
e
a
N
e
a
r
e
s
t
≠
n
u
l
l  then
(9)    t
e
m
p
←
P
.
h
r
z
A
r
e
a
N
e
a
r
e
s
t
(10)  if  t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
≠
n
u
l
l  then
(11)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
(12)   else
(13)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
(14)   end if
(15)  else if  P
.
v
e
r
t
N
e
a
r
e
s
t
≠
n
u
l
l  then
(16)   if  P
.
y
≤
S
h
a
p
e
F
r
a
m
e
.
T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
R
o
o
t
.
min
⁡
Y  then
(17)    T
e
x
t
P
o
r
t
i
o
n
←
P
.
h
r
z
N
e
a
r
e
s
t
(18)   else
(19)    t
e
m
p
← the TextPortion which has the biggest max
⁡
Y
-
min
⁡
Y
(20)   if  t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
≠
n
u
l
l  then
(21)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
(22)   else
(23)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
(24)   end if
(25)  end if
(26) end if
(27) return  T
e
x
t
P
o
r
t
i
o
n


### 3.2. Operation of Selecting Letters

When the cursor is examined as locating at a letter zone, this letter zone should be identified. There are two kinds of models for the letter zone selection, namely, starting or ending control tags. Intuitively, there are a pair of tags produced by the application located at the nearestTextPortion for the letter zone to be selected, which is surrounding therectangle of theTextPortion by the starting and ending control tags. These two tags can be dragged for covering the whole letter zone. In the following, we introduce the rules of locating the starting or ending control tag.The scenario of starting control tag is shown in Figure4. Generally, when the starting control tag is dragged into the letter zone, the spatial index will retrieve therectangle which is nearest to or containedby the location where this tag locates. Otherwise, this tag is dragged to one of the other eight zones, and the rules are described as follows.(i)
Zone a. The starting control tag should be located before the firstTextPortion of the first line.
(ii)
Zone b. The starting control tag should be located before the correspondingTextPortion of the first line.
(iii)
Zone c. The starting control tag should be located before the firstTextPortion of the second line.
(iv)
Zone d. The starting control tag should be located before the firstTextPortion of the line which is nearest to the location point.
(v)
Zone e. The starting control tag should be located before the firstTextPortion of the line which is the next line of the line nearest to the location point.
(vi)
Zone f. The starting control tag should be located before the firstTextPortion of the last line.
(vii)
Zone g. The starting control tag should be located before the correspondingTextPortion of the last line.
(viii)
Zone h. The starting control tag should be located before the lastTextPortion of the last line.Figure 4
Scenario for starting control tag.The scenario of ending control tag is shown in Figure5. Similarly, the ending control tag is processed in a similar fashion as that of the starting control tag, and thus we avoid the details of the handling procedure.Figure 5
Scenario for ending control tag.Thereafter, the letter zone is selected leveraging the determination of starting and ending control tags, which are actually the similar procedures as the determination of the cursor as presented by Algorithm2. When the starting and ending control tags (denoted bystarTag andendTag) are determined, the letter zone is determined, which is arectangle such thatstarTag is the upper-left coordinate, whileendTag is the bottom-right coordinate.


### 3.3. Operation of Generating Guidelines

Users may often require to adjust the position of some objects in the page of the PowerPoint when making the PorwerPoint pages. During the object adjustment, the correspondingShapeFrame should be moved to the target position and guidelines should be identified for locating theShapeFrame and facilitating theShapeFrame transferring. WhenShapeFrame is moved to a place where the bound ofShapeFrame has very little distance to the guideline, the bound should beabsorbed by the guideline automatically. Generally, there are three types of guideline that should be considered forShapeFrame transferring.(i) Alignment Guideline. As shown in Figure 6, when aShapeFrame is to be moved to a location which is to be aligned with anotherShapeFrame, there should be an alignment guide for supporting this transferring. As shown by the figure, the shape of shadow is the the place where therectangle ofShapeFrame will be moved to. The blue line on the top is the alignment guideline produced leveraging the spatial index.Figure 6
Sample of the alignment guideline.(ii) Equidistance Guideline. As shown in Figure 7, when therectangle ofShapeFrame is moved to the area of shadow, the guideline should be produced leveraging the spatial index for supporting this transferring.Figure 7
Sample of the equal distance guideline.(iii) Center Guideline. As shown in Figure 8, when therectangle ofShapeFrame is moved to place where the center of the tworectangles is aligned, the center guide should be produced leveraging the spatial index. Beside a vertical center guideline generated and illustrated by Figure 8, there should be a horizontal center guide to be generated as well.Figure 8
Sample of the center guideline.The procedure of guideline generation is presented by Algorithm3. Generally, the bounds of therectangles for theShapeFrame of original and target are compared leveraging the spatial index constructed in Section 2. If the bounds of original and targetShapeFrame are neighboring, the bounds of targetShapeFrame in the spatial index are used as the guideline and are being added intoalignList. Specifically, given amR, it is examined to check whether it is contained byiR (lines 1–5), and the relation between the original and targetShapeFrame is verified (lines 6–10). At last,mR is examined to check whether it is close to bottom or top ofiR (lines 11–15). The guideline saved inalignList is returned finally (line 16). TheTHRESHOLD is a parameter set by the user, which specifies the size of blank between therectangles.Algorithm 3:Generating the guideline.
Require:
m
R: the rectangle of S
h
a
p
e
F
r
a
m
e moved by user.
i
R: the rectangles of S
h
a
p
e
F
r
a
m
e which is saved in the spatial index.
Ensure:
a
l
i
g
n
L
i
s
t: the set of guide lines to be generated.
(1)  if  m
R
.
min
⁡
Y
-
i
R
.
min
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(2)   add y
=
i
R
.
min
⁡
Y into a
l
i
g
n
L
i
s
t
(3)   if  m
R
.
max
⁡
Y
-
i
R
.
max
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(4)    add y
=
i
R
.
max
⁡
Y into a
l
i
g
n
L
i
s
t
(5)   end if
(6)  else if  m
R
.
min
⁡
Y
-
i
R
.
max
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(7)   add y
=
i
R
.
max
⁡
Y into a
l
i
g
n
L
i
s
t
(8)   if  m
R
.
max
⁡
Y
-
i
R
.
min
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(9)    add y
=
i
R
.
min
⁡
Y into a
l
i
g
n
L
i
s
t
(10)  end if
(1
1) else if  m
R
.
max
⁡
Y
-
i
R
.
min
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(1
2)  add y
=
i
R
.
min
⁡
Y into a
l
i
g
n
L
i
s
t
(1
3) else if  m
R
.
max
⁡
Y
-
i
R
.
max
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(1
4)  add y
=
i
R
.
max
⁡
Y into a
l
i
g
n
L
i
s
t
(1
5) end if
(1
6) return  a
l
i
g
n
L
i
s
t


## 3.1. Operation of Locating a Cursor

Cursor location is basically locating apoint in the page of PowerPoint. The model ofpoint retrieve object is shown in Figure 3, where there are two types of zones in a simple page of a PowerPoint, which are (i) letter zones and (ii) zones around the letters. Generally, when we touch the page by fingers, we are giving the instruction of producing a cursor by the location where we have touched.(i)
When the finger point is located upon the letters, this means that thepoint retrieve object is located in the letters zone. In this case, the spatial index will (i) retrieve therectangle which is nearest to or containedby thepoint retrieve object and (ii) produce the cursor after theTextPortion mapping to therectangle.
(ii)
Otherwise, thepoint retrieve object is located in the zone around the letters, and there will be eight conditions that determine the location of the cursor as follows.
(a)
Zone a. The cursor should be located before the firstTextPortion of the first line.
(b)
Zone b. The cursor should be located after the correspondingTextPortion of the first line.
(c)
Zone c. The cursor should be located after the lastTextPortion of the first line.
(d)
Zone d. The cursor should be located before the firstTextPortion of the line which is nearest to thepoint retrieve object.
(e)
Zone e. The cursor should be located after the lastTextPortion of the line which is nearest to thepoint retrieve object.
(f)
Zone f. The cursor should be located before the firstTextPortion of the last line.
(g)
Zone g. The cursor should be located after the correspondingTextPortion of the last line.
(h)
Zone h. The cursor should be located after the lastTextPortion of the last line.Figure 3
The model of apoint retrieve object.The procedure of locating the cursor based on the location of finger point is described by Algorithm2. Note that the spatial index ofTextPortion constructed in Section 2 improves the performance ofrectangle retrieving. Firstly,TextPortion is initialized asnull (line 1). The spatial indexTextPortionRTree is retrieved to examine whether there is aTextPortion containing the location where the finger point locates (lines 2–7). If the point is located in a certainTextPortion, the procedure terminates and the currentTextPortion is returned (line 5). Otherwise, the spatial relationship ofnearest is used for determining whetherTextPortion and the finger point are in the relation of horizontal (line 8) or vertical (line 15) situations and retrievingTextPortion which is nearest the finger point. Thereafter,TextPortion is expanded as arectangle of the row and usesareaHrzNearest to find aTextPortion where the cursor should be covered (lines 8–14 and lines 15–26). Note that this is different fromnearest for the horizontal and vertical situations. WhenVertNearest
≠
n
u
l
l, we will verify whether the finger point is under all of theTextPortion and returnHrzNearest when the finger point is at the bottom (lines 16-17). The time complexity is O
(
n
), where n is the number of spatial objects.Algorithm 2:Locating the cursor.
Require:
P: the point where the finger locates
Ensure:
T
e
x
t
P
o
r
t
i
o
n: TextPortion where the cursor locates
(1)   T
e
x
t
P
o
r
t
i
o
n
←
n
u
l
l
(2)   while  S
h
a
p
e
F
r
a
m
e
.
T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
C
u
r
r
e
n
t
≠
n
u
l
l  do
(3)    if  T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
C
u
r
r
e
n
t  c
o
n
t
a
i
n
s  P  then
(4)     T
e
x
t
P
o
r
t
i
o
n
←
T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
C
u
r
r
e
n
t
(5)     return  T
e
x
t
P
o
r
t
i
o
n
(6)    end if
(7)   end while
(8)   if  P
.
h
r
z
A
r
e
a
N
e
a
r
e
s
t
≠
n
u
l
l  then
(9)    t
e
m
p
←
P
.
h
r
z
A
r
e
a
N
e
a
r
e
s
t
(10)  if  t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
≠
n
u
l
l  then
(11)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
(12)   else
(13)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
(14)   end if
(15)  else if  P
.
v
e
r
t
N
e
a
r
e
s
t
≠
n
u
l
l  then
(16)   if  P
.
y
≤
S
h
a
p
e
F
r
a
m
e
.
T
e
x
t
P
o
r
t
i
o
n
R
T
r
e
e
.
R
o
o
t
.
min
⁡
Y  then
(17)    T
e
x
t
P
o
r
t
i
o
n
←
P
.
h
r
z
N
e
a
r
e
s
t
(18)   else
(19)    t
e
m
p
← the TextPortion which has the biggest max
⁡
Y
-
min
⁡
Y
(20)   if  t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
≠
n
u
l
l  then
(21)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
.
e
x
p
a
n
d
T
o
R
o
w
.
a
r
e
a
H
r
z
N
e
a
r
e
s
t
(22)   else
(23)    T
e
x
t
P
o
r
t
i
o
n
←
t
e
m
p
(24)   end if
(25)  end if
(26) end if
(27) return  T
e
x
t
P
o
r
t
i
o
n


## 3.2. Operation of Selecting Letters

When the cursor is examined as locating at a letter zone, this letter zone should be identified. There are two kinds of models for the letter zone selection, namely, starting or ending control tags. Intuitively, there are a pair of tags produced by the application located at the nearestTextPortion for the letter zone to be selected, which is surrounding therectangle of theTextPortion by the starting and ending control tags. These two tags can be dragged for covering the whole letter zone. In the following, we introduce the rules of locating the starting or ending control tag.The scenario of starting control tag is shown in Figure4. Generally, when the starting control tag is dragged into the letter zone, the spatial index will retrieve therectangle which is nearest to or containedby the location where this tag locates. Otherwise, this tag is dragged to one of the other eight zones, and the rules are described as follows.(i)
Zone a. The starting control tag should be located before the firstTextPortion of the first line.
(ii)
Zone b. The starting control tag should be located before the correspondingTextPortion of the first line.
(iii)
Zone c. The starting control tag should be located before the firstTextPortion of the second line.
(iv)
Zone d. The starting control tag should be located before the firstTextPortion of the line which is nearest to the location point.
(v)
Zone e. The starting control tag should be located before the firstTextPortion of the line which is the next line of the line nearest to the location point.
(vi)
Zone f. The starting control tag should be located before the firstTextPortion of the last line.
(vii)
Zone g. The starting control tag should be located before the correspondingTextPortion of the last line.
(viii)
Zone h. The starting control tag should be located before the lastTextPortion of the last line.Figure 4
Scenario for starting control tag.The scenario of ending control tag is shown in Figure5. Similarly, the ending control tag is processed in a similar fashion as that of the starting control tag, and thus we avoid the details of the handling procedure.Figure 5
Scenario for ending control tag.Thereafter, the letter zone is selected leveraging the determination of starting and ending control tags, which are actually the similar procedures as the determination of the cursor as presented by Algorithm2. When the starting and ending control tags (denoted bystarTag andendTag) are determined, the letter zone is determined, which is arectangle such thatstarTag is the upper-left coordinate, whileendTag is the bottom-right coordinate.


## 3.3. Operation of Generating Guidelines

Users may often require to adjust the position of some objects in the page of the PowerPoint when making the PorwerPoint pages. During the object adjustment, the correspondingShapeFrame should be moved to the target position and guidelines should be identified for locating theShapeFrame and facilitating theShapeFrame transferring. WhenShapeFrame is moved to a place where the bound ofShapeFrame has very little distance to the guideline, the bound should beabsorbed by the guideline automatically. Generally, there are three types of guideline that should be considered forShapeFrame transferring.(i) Alignment Guideline. As shown in Figure 6, when aShapeFrame is to be moved to a location which is to be aligned with anotherShapeFrame, there should be an alignment guide for supporting this transferring. As shown by the figure, the shape of shadow is the the place where therectangle ofShapeFrame will be moved to. The blue line on the top is the alignment guideline produced leveraging the spatial index.Figure 6
Sample of the alignment guideline.(ii) Equidistance Guideline. As shown in Figure 7, when therectangle ofShapeFrame is moved to the area of shadow, the guideline should be produced leveraging the spatial index for supporting this transferring.Figure 7
Sample of the equal distance guideline.(iii) Center Guideline. As shown in Figure 8, when therectangle ofShapeFrame is moved to place where the center of the tworectangles is aligned, the center guide should be produced leveraging the spatial index. Beside a vertical center guideline generated and illustrated by Figure 8, there should be a horizontal center guide to be generated as well.Figure 8
Sample of the center guideline.The procedure of guideline generation is presented by Algorithm3. Generally, the bounds of therectangles for theShapeFrame of original and target are compared leveraging the spatial index constructed in Section 2. If the bounds of original and targetShapeFrame are neighboring, the bounds of targetShapeFrame in the spatial index are used as the guideline and are being added intoalignList. Specifically, given amR, it is examined to check whether it is contained byiR (lines 1–5), and the relation between the original and targetShapeFrame is verified (lines 6–10). At last,mR is examined to check whether it is close to bottom or top ofiR (lines 11–15). The guideline saved inalignList is returned finally (line 16). TheTHRESHOLD is a parameter set by the user, which specifies the size of blank between therectangles.Algorithm 3:Generating the guideline.
Require:
m
R: the rectangle of S
h
a
p
e
F
r
a
m
e moved by user.
i
R: the rectangles of S
h
a
p
e
F
r
a
m
e which is saved in the spatial index.
Ensure:
a
l
i
g
n
L
i
s
t: the set of guide lines to be generated.
(1)  if  m
R
.
min
⁡
Y
-
i
R
.
min
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(2)   add y
=
i
R
.
min
⁡
Y into a
l
i
g
n
L
i
s
t
(3)   if  m
R
.
max
⁡
Y
-
i
R
.
max
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(4)    add y
=
i
R
.
max
⁡
Y into a
l
i
g
n
L
i
s
t
(5)   end if
(6)  else if  m
R
.
min
⁡
Y
-
i
R
.
max
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(7)   add y
=
i
R
.
max
⁡
Y into a
l
i
g
n
L
i
s
t
(8)   if  m
R
.
max
⁡
Y
-
i
R
.
min
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(9)    add y
=
i
R
.
min
⁡
Y into a
l
i
g
n
L
i
s
t
(10)  end if
(1
1) else if  m
R
.
max
⁡
Y
-
i
R
.
min
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(1
2)  add y
=
i
R
.
min
⁡
Y into a
l
i
g
n
L
i
s
t
(1
3) else if  m
R
.
max
⁡
Y
-
i
R
.
max
⁡
Y
<
T
H
R
E
S
H
O
L
D  then
(1
4)  add y
=
i
R
.
max
⁡
Y into a
l
i
g
n
L
i
s
t
(1
5) end if
(1
6) return  a
l
i
g
n
L
i
s
t


## 4. Implementation and Evaluation

Figure9 shows the class hierarchy for the implementation, which is programmed in Java. Generally, theClass RTree abstracts theTextPortion and theShapeFrame into theClass rectangle, which has five parameters includingminX,maxX,minY,maxY, andowner. Based on the ClassRectangle, a spatial object has been described as a rectangle with absolute coordinate value. This strategy changes the way of displaying the object by describing the object with the coordinates rather than the parameters such aswidth andheight in theClass Textportion. Thus, spatial objects retrieving is simplified somehow, where the calculation based on the coordinates of spatial objects is unnecessary.Figure 9
Class hierarchy for the implementation of indexing spatial objects in mobile PowerPoint pages.The experiments have been conducted on the helpdesk (Lenovo 3000), the pad (ONDA v972), and the smart phone (Sony LT29i), where the operation system of Sony LT2i and ONDA v972 is the Android system. The experiment is conducted as follows. Some English words are generated in a PowerPoint page, and these words are classified into 9 zones as shown in Figure10. For each operation, we conduct it in each zone 10 times, with or without applying our technique. The accuracy of the experiments for these operations is computed as follows.Figure 10
Classification of zones.The comparison of locating the cursor is shown in Table2. The accuracy for the case of noused spatial index is 31
/
90
≈
0.344, while that for the case of using our technique is 83
/
90
≈
0.922, for the experiments in all zones. Table 2 shows that the cursor has not been successfully located in the following zones: Zones a, d, and f, for the case of noused spatial index. Our investigation shows that traditional indexing methods search the nearest position when locating the cursor. In these three zones, the rules specified at Section 3.1 cannot be satisfied any longer. When our spatial index has been applied, the application will retrieve the nearestTextPortion and locate the cursor behind theTextPortion. Similarly, traditional indexing methods can work well in Zones c, e, and h. As to Zones b, I, and g, an average accuracy rate is returned for the case of noused spatial index, since there could be some cases when we point at a blank space which can satisfy the principle coincidentally. When our spatial index is applied, the cursor could be located behind theTextPortion where we point at, and there may have some wrong rows in some situations.Table 2
Comparison of the accuracy for locating the cursor.
Zone
Nonused spatial index
Used spatial index
Frequency
Correct
Frequency
Correct
Zone a
10
0
10
10
Zone b
10
3
10
8
Zone c
10
6
10
10
Zone d
10
0
10
9
Zone e
10
4
10
8
Zone f
10
0
10
10
Zone g
10
3
10
9
Zone h
10
10
10
10
Zone i
10
5
10
9
Sum
90
31
90
83Tables3 and 4 show the accuracy for locating the starting and ending control tags. The accuracy for the case of noused spatial index is 45
/
90
=
0.5 for locating the starting control tag and is 42
/
90
≈
0.467 for locating the ending control tag, while that for the case of using our technique is 82
/
90
≈
0.911 for locating the starting control tag and is 84
/
90
≈
0.933 for locating the ending control tag, according to the experiments in all zones. We can see that the accuracy for the case of noused spatial index is not very low. Actually, when traditional indexing method is applied for generating the starting control tag, the principle can be satisfied somehow. For instance, when pointing at Zones a, d, and f, the traditional index gets the nearest position that could be located. However, traditional indexing methods cannot work well in Zones a, d, and f, since the position to be located is before the firstTextPortion in the next row of the corresponding position. The similar situation exists for the case of ending control tag.Table 3
Comparison of the accuracy for locating starting control tag.
Zone
Nonused spatial index
Used spatial index
Frequency
Correct
Frequency
Correct
Zone a
10
10
10
10
Zone b
10
7
10
8
Zone c
10
0
10
9
Zone d
10
8
10
9
Zone e
10
0
10
8
Zone f
10
6
10
10
Zone g
10
5
10
9
Zone h
10
0
10
10
Zone i
10
9
10
9
Sum
90
45
90
82Table 4
Comparison of the accuracy for locating ending control tag.
Zone
Nonused spatial index
Used spatial index
Frequency
Correct
Frequency
Correct
Zone a
10
0
10
10
Zone b
10
8
10
8
Zone c
10
5
10
10
Zone d
10
0
10
9
Zone e
10
6
10
9
Zone f
10
0
10
10
Zone g
10
4
10
9
Zone h
10
10
10
10
Zone i
10
9
10
9
Sum
90
42
90
84


## 5. Related Work

With the rapid development and wide applicability of cloud computing and the mobile internet technologies, there is a trend that people can build vehicles, devices, goods, and everyday objects to become a part of the Internet of things [18–20]. Mobile devices are to be used more widely and ubiquitously, which leads the mobile office application to become a hot research and engineering topic. In the following, we review and discuss the related techniques in this domain.With the cloud going into our life, there are many researchers trying to deploy applications on the cloud platform to settle the problem of low capabilities of mobile devices. Reference [21] built a mobile OA system based on 3G network, WAP, and J2EE. It was used to fill up the deficiency of traditional OA system and to create an application environment for extending the business to user’s mobile phones. Thus, it refrains from the disadvantages that the traditional OA system can only be used in offices or other places connected to the Internet, which has limited the use of the OA system largely. This is actually a hint for us to expand our mobile office application to make use of the mobile network, such as using the cloud to save the documents of mobile applications. Reference [22] presents the motivation and preliminary design for a framework to create ad hoc cloud computing providers. By this, they create a cloud among the mobile in the vicinity devices to facilitate the application on these devices to execute jobs. They also show their perspective that the usage of mobility traces will be considered to create table communities and not only places. This work reminds us that we could deploy our office application on the platform to reduce the computing pressure of single device. Reference [23] presents an algorithm of location-based services (LBS) on the mobile devices to save the battery of these devices. By using the promoted quadtrees, the devices could save the number of requests to the LBS server when detecting the surrounding area of interest. Thus, the battery of the devices can be extended largely. Generally, they have the similar idea with us that using the spacial index to promote the capabilities of mobile devices. It happens that there is a similar case, [24] making an exploration on whether the cloud can save the energy of mobile devices. This work explores the impact of cloud-based applications on the battery life of mobile devices. Specifically, it tries to answer the following question.For some user defined application performance criteria, when is the usage of cloud-based applications more preferable in terms of energy consumption than non-cloud based applications that are executed locally on users device? Reference [25] aims to use the mobile cloud computing to help bridging the gap between the capabilities of mobile devices and the need of rich applications. Cloud computing can provide mobile applications with the capabilities of cloud servers and storage together with the benefits of mobile devices and mobile connectivity, possibly enabling a new generation of truly ubiquitous multimedia applications on mobile devices: Cloud Mobile Media (CMM) applications. The office application can be classified into CMM. So we can take the cloud computing into consideration to make a promotion from the performance perspective. In general, the cloud is used by people to promote the customer experience on extending the memory or extending the compute capacity, and it also can be used to save the energy of the devices. These instances inspire us to an extent, and we should exploit the potentialities of cloud to optimize the smart devices.To response, the requirement of mobile office [26] has changed the traditional rich client to a browser-based thin client. So all the stuff operated on the client of the mobile devices can be deployed and executed at the server. Reference [27] argues that the mobile application has many advantages in different aspects. Thus, the browser-based thin client cannot replace the mobile application completely. Reference [13] has proposed a similar target to optimize the application with us. This work aims to implement web services for mobile devices limited by the physically constrained of mobile devices, such as, low processor speed, limited memory, limited memory, and slow wireless connection. The authors have evaluated the RESTful web service for mobile devices with respect to conventional SOAP web services. Experiments show that RESTful web services outperform conventional SOAP web services. Reference [28] indicates that a cloud mobile office system can satisfy the business enterprise personnel requirement, which is to access enterprise information resources anytime and anywhere and using any devices. The design of cloud mobile office system framework does not affect the original office system; it is very good for the stability of the primary system. It is a total solution for the enterprise office automation in the mobile Internet environment. Our research can be a promotion on the application of the mobile devices. Reference [29] presents some directions for mobile application software engineering. It can be a guide when developing the mobile office application. In general, these works indicate that there will be great changes in the programming work of the application on smart devices. It can be a thin-client or can be a node of a web service.From the discussion above, we can see that the efficiency of the applications running on mobile devices is still a challenge to be addressed. Consequently, we have promoted the accuracy of some operations for the mobile PowerPoint software by using the spatial indexing mechanism. As [30] mentioned, an extensive research has been carried out on the multidimensional indexing, and we can treat spatial index as a kind of special multidimensional indexing mechanism for enabling efficient range queries. They have made the comparison between several kinds of spatial indexing methods to find the one that performs the best in high multidimensional indexing queries. It is the typical application of spatial index on the nonspatial field and happens when there is a similar case. Reference [31] proposes an approach through using the spatial index to handle the multidimensional range query. Different from [30], this work focuses on conducting the research on the GPU. Reference [32] has inspired us with applying the spatial index on the storage of the nonspatial data with coordinates, where R∗-tree can be used in the image storage process. Reference [33] compares some kinds of spatial index and argues that R∗-tree, which is a revision of the R-tree, could perform excellent being performance within a DBMS. As [34] presented, the authors have proposed an optimization algorithm for creating R-tree indexing structure based on spatial clustering, and this indexing mechanism can be used as a dynamic indexing structure for spatial databases. These works show us that the spatial index can be used in the no-spatial situations. As the spatial indexes are highly efficient, they can be used in multidimensional applications such as image indexing and PowerPoint page. These lead us to explore a wide range of applications of spatial index.To summarize, the mobile office applications need to be optimized to face the imperfection of current smart devices and satisfy the user friendliness of the application. We have used the spatial index to optimize the experience of some of the operations of mobile office.


## 6. Conclusion

Unlike the traditional office software, due to the limited storage and computational capability of mobile devices, how to support the page editing in a fast and energy-efficient manner is fundamental. Generally, an efficient spatial indexing mechanism can help mobile office software quickly locate spatial objects. Therefore, it promotes the speed of operations on the spatial object and satisfies the need of quick response of the user. In this paper, we have proposed an approach to address this challenge. Specifically, an MR∗-tree based indexing mechanism has been developed for facilitating the fast and energy-efficient retrieval of spatial objects in mobile PowerPoint pages. Based on that, techniques are developed to support the operations when editing mobile PowerPoint pages. We have implemented the prototype which has been deployed on the computer, the pad, and the smart phone. The experimental evaluation shows that the considerable improvement on the accuracy for the operations is to be performed on spatial objects in the mobile PowerPoint pages.



---

*Source: 372486-2015-10-19.xml*