Truy vấn hướng đối tượng dựa trên đồ thị chữ ký nhị phân

Truy vấn hướng đối tượng . . .

TRUY VẤN HƯỚNG ĐỐI TƯỢNG DỰA TRÊN

ĐỒ THỊ CHỮ KÝ NHỊ PHÂN

Trương Công Tuấn^*, Trần Minh Bảo^**

TÓM TẮT

Bài báo xây dựng một mô hình cấu trúc đồ thị để tổ chức lưu trữ chữ ký của các đối tượng

trong cơ sở dữ liệu hướng đối tượng, trong đó các đối tượng được mã hóa và xây dựng dưới dạng

một đồ thị chữ ký, từ đó xây dựng thuật toán để xử lý truy vấn trên đồ thị chữ ký và đề xuất mô

hình ứng dụng.

Từ khoá: hướng đối tượng cơ sở dữ liệu; cơ cấu chỉ số; chữ ký; tập tin chữ ký; đồ thị chữ ký

OBJECT-ORIENTED QUERY PROCESSING BASED BINARY

SIGNATURE GRAPH

ABSTRACT

In this paper, we construct a graph structure model to store object signatures in object-

oriented databases, in which the objects are hash encoded and presented by a signature graph.

Then we built an algorithm to process the query on signature graph and propose an application

model.

Keyword: Object-oriented database; index structure; signature; signature ile; signature graph.

1. ĐẶT VẤN ĐỀ

tượng trên cây chữ ký SD-Tree [3], truy vấn

Truy vấn trực tiếp trên các đối tượng trong đối tượng trong cơ sở dữ liệu hướng đối tượng

cơ sở dữ liệu hướng đối tượng rất tốn kém chi dựa trên cấu trúc cây chữ ký đối tượng [2], xây

phí lưu trữ dữ liệu trong quá trình truy vấn dựng cấu trúc tập tin chữ ký và cây chữ ký [8],

và tốn nhiều thời gian để thực hiện truy vấn xây dựng cấu trúc đồ thị chữ ký dựa trên tập tin

trên hệ thống dữ liệu thực. Bài toán đặt ra là chữ ký để truy vấn trong cơ sở dữ liệu hướng

cần mô tả lại hệ thống dữ liệu đơn giản hơn đối tượng [9, 12], xây dựng cấu trúc cây chữ ký

và xây dựng cấu trúc dữ liệu tương ứng để có để giảm không gian tìm kiếm dữ liệu [1, 2, 7,

thể giảm không gian tìm kiếm trong quá trình 10], truy vấn dữ liệu trên tập tin văn bản bằng

thực thi câu truy vấn mà vẫn đảm bảo được tập tin chữ ký tuần tự và tập tin chữ ký phân

việc truy vấn được các đối tượng cần thiết.

mảnh [4], tạo chỉ mục truy vấn cho các tập tin

Các phương pháp truy vấn dựa trên chữ văn bản [5, 6], tạo cấu trúc cây chữ cân bằng

ký nhị phân đã công bố như: truy vấn đối và thao tác trên cây chữ ký cân bằng [1, 8],…

^*PGS.TS. Trường Đại học Khoa học, Đại học Huế. E-Mail: tctuan_it_dept@yahoo.com

^**ThS. GV. Trường Đại học Công nghiệp Thực phẩm Tp.HCM. E-Mail: tmbaovn@gmail.com

59

Tạp chí Kinh tế - Kỹ thuật

Bài báo sẽ tiếp cận phương pháp tạo chữ

ký cho các đối tượng, từ đó xây dựng cấu trúc

đồ thị để tham chiếu đến cơ sở dữ liệu thực.

Chữ ký nhỏ hơn rất nhiều so với đối tượng

thực, khoảng từ 10% – 20% so với đối tượng

[4, 5, 8]. Chữ ký của các đối tượng sẽ được

lưu trữ trong tập tin chữ ký và qua đó thực

hiện phép truy vấn các đối tượng dựa trên tập

tin chữ ký này. Ngoài ra, để việc tìm kiếm

hiệu quả hơn, cần xây dựng cấu trúc dữ liệu

lưu trữ tập tin chữ ký. Cấu trúc lưu trữ tập

tin chữ ký này có thể dưới dạng các tập tin

chữ ký tuần tự, các tập tin chữ ký phân mảnh,

cấu trúc cây chữ ký, cấu trúc dạng đồ thị chữ

ký,… các cấu trúc lưu trữ tập tin chữ ký sẽ

làm giảm không gian tìm kiếm và tối ưu quá

trình truy vấn dữ liệu.

giá trị thuộc tính. Chữ ký của một giá trị thuộc

tính là một chuỗi bít được mã hóa bằng hàm

băm, có độ dài với bít 1 và bít 0. Chữ ký đối

tượng được xây dựng bằng phép toán OR bít

cho tất cả các chữ ký của các giá trị thuộc tính

của đối tượng [1].

Các chữ ký đối tượng của một lớp được

lưu trữ trong một tập tin, gọi là tập tin chữ

ký. Tập tin chữ ký tuần tự SSF (Sequential

Signature File) gồm các chữ ký đối tượng

được lưu trữ tuần tự [1, 3, 8].

Một câu truy vấn chỉ định các giá trị cần

tìm kiếm cũng sẽ được mã hóa thành chữ ký

truy vấn giống như cách mã hóa chữ ký các

giá trị thuộc tính của đối tượng. Lúc đó chữ

ký truy vấn được so sánh đối với mọi chữ ký

đối tượng trong tập tin chữ ký. Có ba trường

hợp có thể xảy ra:

Bài báo mô tả lại hệ thống dữ liệu thực

trở thành một cấu trúc dữ liệu tham chiếu có

không gian tìm kiếm nhỏ hơn để từ đó giảm

thời gian truy vấn dữ liệu và đồng thời cấu

1. Đối tượng phù hợp với câu truy vấn,

nghĩa là đối với mọi tập bít trong chữ ký truy

, tập bít tương ứng trong chữ ký đối

vấn s_q

trúc dữ liệu tham chiếu trung gian này có thể tượng s cũng chính là nó, tức là s_q∧ s = s_q;

truy vấn ngược lại dữ liệu thực sự. Kết quả

2. Đối tượng không phù hợp với câu truy

của bài báo sẽ tập trung vào việc xây dựng vấn, nghĩa là s_q∧ s ≠ s_q;

cấu trúc lưu trữ tập tin chữ ký dưới dạng đồ

3. Chữ ký được đối sánh và cho ra một kết

thị chữ ký và thuật toán truy vấn đối tượng quả phù hợp nhưng đối tượng không phù hợp

trên đồ thị chữ ký đồng thời xây dựng mô với điều kiện tìm kiếm trong câu truy vấn.

hình ứng dụng.

Để loại ra trường hợp này, các đối tượng phải

Phần đầu của bài báo sẽ giới thiệu khái được kiểm tra sau khi các chữ ký đối tượng

quát về chữ ký cho các đối tượng; tiếp theo được đối sánh phù hợp.

bài báo giới thiệu các khái niệm cơ bản về chữ

Một ví dụ về chữ ký của đối tượng được

ký và cấu trúc đồ thị chữ ký; sau đó bài báo minh họa như hình sau:

thực hiện xây dựng đồ thị chữ ký và thuật toán

truy vấn đối tượng trên đồ thị chữ ký đồng

thời xây dựng mô hình ứng dụng; phần cuối

cùng là kết luận.

2. CÁC KHÁI NIỆM CƠ SỞ

2.1. Chữ ký đối tượng

Trong một cơ sở dữ liệu hướng đối tượng,

mỗi đối tượng được biểu diễn bởi một tập các

Hình 1. Một ví dụ về chữ ký của đối tượng.

60

Truy vấn hướng đối tượng . . .

2.2. Đồ thị chữ ký

tạp của việc tách nút là O(l³), với l là số chữ

Định nghĩa 1. Một đồ thị chữ ký G đối ký trên một trang nút lá [11]. Để giải quyết

với tập tin chữ ký S = s₁.s₂…s_n, trong đó s_i≠ s_jbài toán lưu trữ cơ sở dữ liệu hướng đối tượng

(i≠j) và |s_k| = m với k = 1,…, n, là một đồ thị và lưu trữ các đối tượng gần giống nhau trong

G = (V, E) sao cho:

cơ sở dữ liệu hướng đối tượng, cần phải xây

1. Mỗi nút v∈V có dạng (p, skip) với p là dựng một đồ thị chữ ký G_scó cấu trúc nhị

con trỏ, trỏ đến chữ ký s trong S và skip là một phân nhưng vẫn có thể lưu trữ được danh sách

số nguyên i không âm, gọi là bước nhảy bít. các chữ ký và cho phép truy ngược lại vị trí

Nếu i > 0, bít thứ i của s_qsẽ được kiểm tra khi của dữ liệu tương ứng, ta xây dựng một cấu

tìm kiếm. Nếu i = 0, s sẽ được so sánh với s_q. trúc G_snhư sau:

2. Đặt e = (u,v)∈E. Lúc đó e được gán

Định nghĩa 3. Đồ thị chữ ký G_scủa lớp

nhãn là 0 hoặc 1 và skip(u)>0. Đặt skip(u)=i. đối tượng có dạng: G_j(r_j; v₁,…, v_n), với G_jmô

Nếu e được gán nhãn là 0 và i>0 thì bít thứ i tả đồ thị chữ ký của lớp đối tượng thứ j, r_jlà

của chữ ký được trỏ bởi p(v) là 0. Nếu e được nút gốc của đồ thị G_jvà v₁,…, v_nlà các nút của

gán nhãn là 1 và i>0 thì bít thứ i của chữ ký đồ thị G_j. Mỗi nút u trong đồ thị G_jcó dạng:

được trỏ p(v) là 1. Một nút v với skip(u) = 0 < lp(u), skip (u) >, với lp(u) là danh sách các

thì không có nút con.

con trỏ tham chiếu đến các vị trí của chữ ký

Định nghĩa 2. Cho S = s₁.s₂…s_nlà tập tin sig(u) trong tập tin chữ ký của lớp đối tượng

chữ ký. Xét s_i(1 ≤ i ≤ n). Nếu tồn tại dãy và skip(u) là bước nhảy bít.

j₁,…, j_hsao cho với mọi k ≠ i (1 ≤ k ≤n) ta có

Ví dụ như hình vẽ sau đây minh họa tập

s_i(j₁,…, j_h) ≠ s_k(j₁,…,j_h), lúc đó ta nói s_i(j₁,…, tin chữ ký và đồ thị chữ ký:

j_h) định danh chữ ký s_ihoặc s_i(j₁,…,j_h) là một

định danh của s_iđối với S.

3. XÂY DỰNG ĐỒ THỊ CHỮ KÝ VÀ

THUẬT TOÁN TRUY VẤN ĐỐI TƯỢNG

3.1. Cấu trúc đồ thị chữ ký

Trong tập tin chữ ký có thể sẽ xuất hiện

nhiều chữ ký giống nhau ứng với các đối

tượng có nội dung giống nhau, quá trình truy Hình 2. Tập tin chữ ký và đồ thị chữ ký

vấn cần tìm ra tất cả vị trí xuất hiện của đối

Tại mỗi nút của đồ thị chữ ký sẽ lưu trữ

tượng phù hợp. Đồ thị chữ ký G theo định danh sách con trỏ tham chiếu đến các chữ ký

nghĩa 1 chỉ có thể lưu trữ các chữ ký đơn lẻ gần giống nhau nhưng có vị trí xuất hiện khác

tại nút và cũng không thể lưu trữ được các nhau trong tập tin chữ ký.

chữ ký giống nhau có tham chiếu đến các đối

tượng trong cơ sở dữ liệu. Hơn nữa, việc lưu

3.2. Thuật toán tạo đồ thị chữ ký

Thuật toán tạo ra đồ thị chữ ký được xây

trữ danh sách các chữ ký có thể sử dụng cây dựng như sau:

S-tree [3, 11] là dạng cây nhiều nhánh cân

bằng tương tự như B+tree, tuy nhiên quá trình

tạo ra cây S-tree và xử lý quá trình tách nút để

cân bằng lại cây tương đối phức tạp, độ phức

Vào: Lớp

Ra: Đồ thị chữ ký

Phương pháp 1. Gen-G_s(lớp)

Begin

61

Tạp chí Kinh tế - Kỹ thuật

objs = {o_j| o_j∈ class, j = 1,…, n}

Lp(root) = null; Sig₁= Hashing(o₁);

Lp(root) = Lp(root) ∪ sig₁;

root = <1, Lp(root)>;

j = 2;

Trong thuật toán tạo đồ thị chữ ký, vì mỗi

lớp là hữu hạn có đối tượng, đặt:

objs={o_j| o_j∈ class, j = 1,…, n}

Do đó, sẽ tạo được tập hữu hạn có chữ ký

đối tượng:

Bước 1. Tạo chữ ký Sig_j= Hashing(o_j);

v ← root;

Qua bước 2;

Sig={sig_j| sig_j= Hashing (oj), j = 1,…, n}

Với mỗi giá trị j, thuật toán sẽ duyệt từ nút

gốc của đồ thị G_sđể đi tìm nút phù hợp, quá

Bước 2. If (v không đánh dấu và skip trình này là hữu hạn vì số nút tạo ra trong đồ

(root) ≠ 0) then Qua bước 3;

Else{i ← Skip(v) đánh dấu v;

If (Sig_v[i] = 1) then v = v→Right;

Else v = v→Left;

thị G_slà hữu hạn. Nên thuật toán sẽ tìm được

nút phù hợp để đưa chữ ký sig_jvào hoặc tạo

ra một nút mới. Vì vậy, sau hữu hạn bước ứng

với giá trị của j = 1,…, n thì thuật toán cho kết

quả là một đồ thị chữ ký G_svới các nút trong

u có dạng < lp(u), skip(u) >.

Quay lại bước 2; }

Bước 3.

If (Sig_j= Sig_v)then

Gọi n là số đối tượng trong một lớp, khi

đó n=|objs|. Đồ thị chữ ký là dạng đồ thị chữ

ký và mỗi lần duyệt đồ thị chữ ký sẽ duyệt

theo nhánh con bên trái hoặc nhánh bên phải,

nên sẽ có 2^(k-1)lần duyệt, với k ≈ 0,1,…, [log₂

{ Lp(v) = Lp(v) ∪ Sig_j;

j ← j + 1; Quay lại bước 1; }

Else{o ← v; s=<sig_j, Lp(s)>; Qua bước 4;}

Bước 4.

Gọi k+1 là vị trí khác nhau đầu tiên giữa n]. Vì có n chữ ký lần lượt đưa vào đồ thị chữ

Sig_jvà Sig_v;

ký G_s, nên số lần duyệt đồ thị tối đa sẽ là: ≈n.

Tuy nhiên, trong đồ thị chữ ký G_ssẽ lần lượt

kiểm tra số bít trên mỗi chữ ký trong quá trình

duyệt đồ thị, gọi m là chiều dài của mỗi chữ

ký, chi phí của thuật toán tạo ra đồ thị chữ

ký G_ssẽ là n.(2.m). Do đó, độ phức tạp trong

trường hợp này sẽ là O(n.m).

Thay thế nút v trở thành:

<k+1, Left(v)=null, Right(v)= null>;

If (Sig_j[k+1] = 1) then

{v → Right = s; v → Left = o;}

Else {v → Right = o; v → Left = s;}

j ← j + 1; Quay lại bước 1;

End.

Một ví dụ về tạo đồ thị chữ ký dựa trên tập tin chữ ký hình 2(a) được minh họa như sau:

Hình 3: Tạo đồ thị chữ ký

62

Truy vấn hướng đối tượng . . .

3.3. Thuật toán truy vấn đối tượng trên sẽ không quay lại một nút sẽ đi qua. Thuật

đồ thị chữ ký

toán sẽ đối sánh chữ ký truy vấn và chữ ký

Sau khi đã tạo ra đồ thị chữ ký G_s, quá tại các nút. Quá trình đối sánh được thực hiện

trình truy vấn hướng đối tượng ứng với yêu trên một hữu hạn các nút của đồ thị G_s. Nên

cầu truy vấn sẽ được thực hiện. Dữ liệu cần sau hữu hạn bước thuật toán sẽ cho ra được

truy vấn sẽ được băm thành dạng chữ ký theo kết quả là một danh sách LP gồm các con trỏ

cùng phương pháp băm chữ ký trên đồ thị G_s, tham chiếu đến các vị trí của chữ ký truy vấn

sau đó sẽ tiến hành tìm kiếm trên đồ thị chữ trong tập tin chữ ký.

ký G_s. Kết quả của quá trình tìm kiếm này là

Trong phương pháp 2, gọi n là số nút đã

một danh sách các con trỏ liên kết đến vị trí được tạo ra trong G_s, mỗi lần duyệt đồ thị có

chữ ký trong tập tin chữ ký của cơ sở dữ liệu thể đi theo hai nhánh của đồ thị G_snên số lần

hướng đối tượng tương ứng.

Thuật toán truy vấn chữ ký sig trên đồ thị Khi đó, chi phí quá trình duyệt đồ thị để tìm

duyệt đồ thị sẽ là 2^k, với k≈0,1,2,…,[log₂n].

G_sđược thực hiện như sau:

kiếm tối đa sẽ là log₂n. Trong mỗi lần duyệt

đồ thị sẽ kiểm tra chữ ký tại các nút để thực

Vào: Chữ ký sig và đồ thị G_s

Ra: Tập các con trỏ Lp liên kết đến các hiện bước nhảy bít và thực hiện đối sánh chữ

chữ ký giống nhau nhưng có vị trí xuất hiện ký tại các nút, giả sử chiều dài của mỗi chữ ký

khác nhau trong tập tin chữ ký.

Phương pháp 2. Search-In-G_s(G_s, sig)

Begin

là m, chi phí quá trình tìm kiếm trên đồ thị G_s

sẽ là 2mlog₂n. Do đó, độ lớn chi phí của thuật

toán sẽ là O(m.logn).

Lp = ∅; v ← root; S = {v};

Bước 1. If (S = ∅ ) then return Lp;

Else Chọn v_j∈ S; S = S \ {vj};

If (v_jđược đánh dấu) then Qua bước 2;

Else { i ← Skip(v_j);

Một ví dụ về tìm kiếm trên đồ thị chữ ký

dựa trên hình 2 được minh họa như sau:

If sig[i] = 0 then

S = S ∪ { vj →right, v_j→left};

Else S = S ∪ {v_j→left};

Quay lại bước 1;

Hình 4: Tìm kiếm trên đồ thị chữ ký

}

Bước 2. If sig được phủ bởi Sig(v_j) then

Lp = Lp ∪ Lp(v_j);

Quay lại bước 1;

Xét tập tin chữ ký và đồ thị chữ ký trên, giả

sử rằng s_q= 1011011 là chữ ký truy vấn, lúc

đó chỉ một phần của đồ thị được tìm kiếm. Để

End.

Đối với phương pháp 2, vì G_sđã tạo ra tìm ra nút v, v được đánh dấu hoặc skip(v) =

trong phương pháp 1 là hữu hạn nên tập S là 0 thì chữ ký của nút v sẽ được kiểm tra tương

một tập hữu hạn chứa các phần tử v_jsẽ được ứng với s_q. Rõ ràng rằng cách tìm kiếm này

duyệt ở các bước tiếp theo.

hiệu quả hơn việc tìm kiếm tuần tự vì chỉ cần

Khi duyệt một nút v_j∈S, thì v_jsẽ được kiểm tra 2 chữ ký, trong khi đó phép duyệt tập

loại ra khỏi tập S. Do đó việc duyệt đồ thị tin chữ ký sẽ kiểm tra 8 chữ ký.

63

Tạp chí Kinh tế - Kỹ thuật

4. XÂY DỰNG MÔ HÌNH ỨNG DỤNG mỗi lớp có nhiều đối tượng. Ứng với mỗi lớp

4.1. Mô hình ứng dụng

sẽ được xây dựng thành một cấu trúc đồ thị

Cấu trúc đồ thị chữ ký được lưu trữ hoàn chữ ký tìm kiếm, đồng thời mỗi đối tượng này

toàn bên trong bộ nhớ chính, trong trường sẽ tạo ra một chữ ký đối tượng. Chữ ký của

hợp này, việc chèn và xóa một chữ ký trên đồ mỗi đối tượng được xây dựng trong mô hình

thị được thực hiện dễ dàng. Tuy nhiên, trong này có chiều dài 128 bit, đó là sự tổ hợp các

cơ sở dữ liệu các tập tin thường rất lớn, vì vậy thuộc tính trong một đối tượng. Toàn bộ cơ sở

đồ thị chữ ký sẽ không thể lưu trữ trên bộ nhớ dữ liệu hướng đối tượng sẽ được phân hoạch

chính mà phải được lưu trữ trên bộ nhớ ngoài. dưới dạng cấu trúc một bảng băm gồm các

Đối với cơ sở dữ liệu hướng đối tượng, chúng chữ ký của đối tượng để thực hiện quá trình

sẽ được lưu trữ và thực thi trên bộ nhớ ngoài. truy vấn.

Cơ sở dữ liệu hướng đối tượng có nhiều lớp,

Hình 5: Mô hình cấu trúc lưu trữ đồ thị chữ ký cho cơ sở dữ liệu hướng đối tượng

4.2. Một ví dụ về mô hình cơ sở dữ liệu đưa ra ở hình 6 đồng thời cũng đưa ra những

hướng đối tượng

quan hệ trên các lớp đối tượng bảng 1. Dựa

Để thực nghiệm truy vấn hướng đối tượng trên mô hình này để thực nghiệm cài đặt cơ sở

trên cơ sở dữ liệu hướng đối tượng. Một ví dụ dữ liệu hướng đối tượng ở mức vật lý.

mô hình cơ sở dữ liệu hướng đối tượng được

Bảng 1. Quan hệ các lớp

S.No Class 1

Class 2

Dept

Relationship

Composition

Aggregation

Generalization

Aggregation

University

1

2

3

4

5

6

7

University

Student

Dept

Student

Programme

Instructor

Male

Student

Programme

Female

Subject

64

Truy vấn hướng đối tượng . . .

Hình 6: Một ví dụ mô hình cơ sở dữ liệu hướng đối tượng

4.3. Xử lý truy vấn trên cơ sở dữ liệu

hướng đối tượng

Để thực hiện việc truy vấn một đối tượng

Bước 2. Đối sánh chữ ký từ khóa để xác

định thuộc lớp cần truy vấn.

Bước 3. Thực hiện truy vấn chữ ký từ

trong cơ sở dữ liệu hướng đối tượng, đầu khóa trên đồ thị chữ ký tương ứng với các lớp

tiên phải chuyển đổi cơ sở dữ liệu hướng đối đã xác định.

tượng thành cấu trúc dữ liệu như trên, ta thực

hiện như sau:

5. KẾT LUẬN

Trong bài báo này, chúng tôi đã đề xuất

Bước 1. Thuộc tính của đối tượng được thuật toán tạo đồ thị chữ ký để lưu trữ các

băm thành chữ ký nhị phân và các thuộc tính chữ ký đối tượng của cơ sở dữ liệu hướng

tạo thành chữ ký đối tượng.

Bước 2. Các chữ ký đối tượng của cùng tượng trên đồ thị chữ ký. Dựa trên cấu trúc đồ

một lớp sẽ tạo thành đồ thị chữ ký.

thị chữ ký đã tạo, bài báo tiến hành đề xuất

Bước 3. Tạo danh sách đồ thị chữ ký mô hình ứng dụng cho cơ sở dữ liệu hướng

tương ứng với từng lớp.

đối tượng. Việc truy vấn trên đồ thị chữ ký

đối tượng và thuật toán truy vấn chữ ký đối

Sau khi có cấu trúc dữ liệu để truy vấn, ta diễn ra tương đối nhanh, do đó có thể áp dụng

thực hiện quá trình truy vấn đối tượng trong phương pháp này trong trường hợp truy vấn

cơ sở dữ liệu hướng đối tượng như sau:

Bước 1. Mã hoá từ khóa cần truy vấn liệu ảnh, các đối tượng multimedia, các đối

thành chữ ký nhị phân.

tượng trong hệ thống thông tin địa lý,…

các đối tượng dữ liệu lớn như đối tượng dữ

65

Tạp chí Kinh tế - Kỹ thuật

TÀI LIỆU THAM KHẢO

1. Yangjun Chen, Yibin Chen, 2006,On the Signature Tree Construction and Analysis, IEEE Trans.

Knowl. Data Eng., 18(9), 1207-1224.

2. Yangjun Chen, 2004, Building Signature Trees into OODBs, Journal of Information Science and

Engineering, 20(2), 275-304.

3. I.E. Shanthi, R. Nadarajan, 2009, Applying SD-Tree for Object-Oriented Query Processing,

Informatica (Slovenia), 33(2), 169-179.

4. D. L. Lee, Y. M. Kim, G. Patel, 1995, Eficient Signature File Methods for Text Retrieval, IEEE

Trans. Knowl. Data Eng., 7(3), 423-435.

5. Walter W.Chang, Hans J. Schek, 1989, A signature Access Method for the Starburst Database

System, Proceedings of the Fifteenth International Conference on Very Large Database, Amsterdam,

145-153.

6. W. C. Lee, D. L. Lee, 1992, Signature File Methods for Indexing Object-Oriented Database systems,

Proceedings of the 2nd International Computer Science Conference, Hong Kong, 616-622.

7. Yangjun Chen, 2006, On the cost of searching signature trees, Science Direct, Information Processing

Letters, 99(1), 19-26.

8. Yangjun Chen, 2002, Signature iles and signature trees, Elsevier Science, Journal Information

Processing Letters, 82(4), 213-221.

9. Yangjun Chen, Yibin Chen, 2004, Signature File Hierarchies and Signature Graphs: a New

Index Method for Object-Oriented Databases, Proceedings of the 2004 ACM symposium on

Applied computing, Nicosia, Cyprus, 724-728.

10. E.Tousidoua, P. Bozanis, Y. Manolopoulos, 2002, Signature-basedstructuresforobjectswithset-

valued attributes, Elsevier Science, Information Systems, 27(2), 93-121.

11. Y.Chen, 2005, On the Signature Trees and Balanced Signature Trees, Proceedings of the 21st

International Conference on Data Engineering, IEEE Computer Society, Tokyo, Japan, 742-753.

12. P.Mahatthanapiwat, 2010, Flexible Searching for Graph Aggregation Hierarchy, Proceedings of the

World Congress on Engineering 2010, London, UK, 405-409.

66